This book constitutes the refereed proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008, held in Pisa, Italy, in June 2008.
The 25 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 78 submissions. The papers address all areas related to combinatorial pattern matching and its applications, such as coding and data compression, computational biology, data mining, information retrieval, natural language processing, pattern recognition, string algorithms, string processing in databases, symbolic computing and text searching.
Author(s): Dan Gusfield (auth.), Paolo Ferragina, Gad M. Landau (eds.)
Series: Lecture Notes in Computer Science 5029 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2008
Language: English
Pages: 317
Tags: Algorithm Analysis and Problem Complexity; Pattern Recognition; Document Preparation and Text Processing; Data Mining and Knowledge Discovery; Computational Biology/Bioinformatics; Data Structures
Front Matter....Pages -
ReCombinatorics: Combinatorial Algorithms for Studying the History of Recombination in Populations....Pages 1-2
Lower Bounds for Succinct Data Structures....Pages 3-3
The Changing Face of Web Search....Pages 4-4
Two-Dimensional Pattern Matching with Combined Scaling and Rotation....Pages 5-17
Searching for Gapped Palindromes....Pages 18-30
Parameterized Algorithms and Hardness Results for Some Graph Motif Problems....Pages 31-43
Finding Largest Well-Predicted Subset of Protein Structure Models....Pages 44-55
HP Distance Via Double Cut and Join Distance....Pages 56-68
Fixed Parameter Tractable Alignment of RNA Structures Including Arbitrary Pseudoknots....Pages 69-81
Faster Algorithm for the Set Variant of the String Barcoding Problem....Pages 82-94
Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics....Pages 95-106
Analysis of the Size of Antidictionary in DCA ....Pages 107-117
Approximate String Matching with Address Bit Errors....Pages 118-129
On-Line Approximate String Matching with Bounded Errors....Pages 130-142
A Black Box for Online Approximate Pattern Matching....Pages 143-151
An(other) Entropy-Bounded Compressed Suffix Tree....Pages 152-165
On Compact Representations of All-Pairs-Shortest-Path-Distance Matrices....Pages 166-177
Computing Inverse ST in Linear Complexity....Pages 178-190
Dynamic Fully-Compressed Suffix Trees....Pages 191-203
A Linear Delay Algorithm for Building Concept Lattices....Pages 204-216
Matching Integer Intervals by Minimal Sets of Binary Words with don’t cares ....Pages 217-229
Fast Algorithms for Computing Tree LCS....Pages 230-243
Why Greed Works for Shortest Common Superstring Problem....Pages 244-254
Constrained LCS: Hardness and Approximation....Pages 255-262
Finding Additive Biclusters with Random Background....Pages 263-276
An Improved Succinct Representation for Dynamic k -ary Trees....Pages 277-289
Towards a Solution to the “Runs” Conjecture....Pages 290-302
On the Longest Common Parameterized Subsequence....Pages 303-315
Back Matter....Pages -
