This book constitutes the refereed proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, CPM 99, held in Warwick, UK in July 1999. The 21 revised papers presented were carefully reviewed and selected from 26 submissions. The papers address all current issues in combinatorial pattern matching dealing with a variety of classical objects like trees, regular expressions, graphs, point sets, and arrays as well as with DNA/RNA coding, WWW issues, information retrieval, data compression, and pattern recognition.
Author(s): Takuya Kida, Masayuki Takeda, Ayumi Shinohara (auth.), Maxime Crochemore, Mike Paterson (eds.)
Series: Lecture Notes in Computer Science 1645
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1999
Language: English
Pages: 304
Tags: Algorithm Analysis and Problem Complexity; Pattern Recognition; Data Structures; Discrete Mathematics in Computer Science; Combinatorics
Shift-And Approach to Pattern Matching in LZW Compressed Text....Pages 1-13
A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed Text....Pages 14-36
Pattern Matching in Text Compressed by Using Antidictionaries....Pages 37-49
On the Structure of Syntenic Distance....Pages 50-65
Physical Mapping with Repeated Probes: The Hypergraph Superstring Problem....Pages 66-77
Hybridization and Genome Rearrangement....Pages 78-87
On the Complexity of Positional Sequencing by Hybridization....Pages 88-100
GESTALT: Genomic Steiner Alignments....Pages 101-114
Bounds on the Number of String Subsequences....Pages 115-122
Approximate Periods of Strings....Pages 123-133
Finding Maximal Pairs with Bounded Gap....Pages 134-149
A Dynamic Data Structure for Reverse Lexicographically Sorted Prefixes....Pages 150-162
A New Indexing Method for Approximate String Matching....Pages 163-185
The Compression of Subsegments of Images Described by Finite Automata....Pages 186-195
Ziv Lempel Compression of Huge Natural Language Data Tries Using Suffix Arrays....Pages 196-211
Matching of Spots in 2D Electrophoresis Images. Point Matching Under Non-uniform Distortions....Pages 212-222
Applying an Edit Distance to the Matching of Tree Ring Sequences in Dendrochronology....Pages 223-242
Fast Multi-dimensional Approximate Pattern Matching....Pages 243-257
Finding Common RNA Secondary Structures from RNA Sequences....Pages 258-269
Finding Common Subsequences with Arcs and Pseudoknots....Pages 270-280
Computing Similarity between RNA Structures....Pages 281-293
