This book constitutes the refereed proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000, held in Montreal, Canada, in June 2000.
The 29 revised full papers presented together with 3 invited contributions and 2 tutorial lectures were carefully reviewed and selected from 44 submissions. The papers are devoted to current theoretical and algorithmic issues of searching and matching strings and more complicated patterns such as trees, regular expression graphs, point sets and arrays as well as to advanced applications of CPM in areas such as Internet, computational biology, multimedia systems, information retrieval, data compression, and pattern recognition.
Author(s): Andrei Z. Broder (auth.), Raffaele Giancarlo, David Sankoff (eds.)
Series: Lecture Notes in Computer Science 1848
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2000
Language: English
Pages: 426
Tags: Algorithm Analysis and Problem Complexity; Pattern Recognition; Document Preparation and Text Processing; Information Storage and Retrieval; Combinatorics
Identifying and Filtering Near-Duplicate Documents....Pages 1-10
Machine Learning for Efficient Natural-Language Processing....Pages 11-11
Browsing around a Digital Library: Today and Tomorrow....Pages 12-26
Algorithmic Aspects of Speech Recognition: A Synopsis....Pages 27-32
Some Results on Flexible-Pattern Discovery....Pages 33-45
Explaining and Controlling Ambiguity in Dynamic Programming....Pages 46-59
A Dynamic Edit Distance Table....Pages 60-68
Parametric Multiple Sequence Alignment and Phylogeny Construction....Pages 69-83
Tsukuba BB: A Branch and Bound Algorithm for Local Multiple Sequence Alignment....Pages 84-98
A Polynomial Time Approximation Scheme for the Closest Substring Problem....Pages 99-107
Approximation Algorithms for Hamming Clustering Problems....Pages 108-118
Approximating the Maximum Isomorphic Agreement Subtree Is Hard....Pages 119-128
A Faster and Unifying Algorithm for Comparing Trees....Pages 129-142
Incomplete Directed Perfect Phylogeny....Pages 143-153
The Longest Common Subsequence Problem for Arc-Annotated Sequences....Pages 154-165
Boyer—Moore String Matching over Ziv-Lempel Compressed Text....Pages 166-180
A Boyer—Moore Type Algorithm for Compressed Pattern Matching....Pages 181-194
Approximate String Matching over Ziv—Lempel Compressed Text....Pages 195-209
Improving Static Compression Schemes by Alphabet Extension....Pages 210-221
Genome Rearrangement by Reversals and Insertions/Deletions of Contiguous Segments....Pages 222-234
A Lower Bound for the Breakpoint Phylogeny Problem....Pages 235-247
Structural Properties and Tractability Results for Linear Synteny....Pages 248-263
Shift Error Detection in Standardized Exams....Pages 264-276
An Upper Bound for Number of Contacts in the HP-Model on the Face-Centered-Cubic Lattice (FCC)....Pages 277-292
The Combinatorial Partitioning Method....Pages 293-304
Compact Suffix Array....Pages 305-319
Linear Bidirectional On-Line Construction of Affix Trees....Pages 320-334
Using Suffix Trees for Gapped Motif Discovery....Pages 335-349
Indexing Text with Approximate q -Grams....Pages 350-363
Simple Optimal String Matching Algorithm....Pages 364-374
Exact and Efficient Computation of the Expected Number of Missing and Common Words in Random Texts....Pages 375-387
Periods and Quasiperiods Characterization....Pages 388-396
Finding Maximal Quasiperiodicities in Strings....Pages 397-411
On the Complexity of Determining the Period of a String....Pages 412-422
