Combinatorial Pattern Matching: 6th Annual Symposium, CPM 95 Espoo, Finland, July 5–7, 1995 Proceedings

Vineet Bafna, S. Muthukrishnan, R. Ravi (auth.), Zvi Galil, Esko Ukkonen (eds.)3540600442, 9783540600442

This volume presents the proceedings of the 6th International Symposium on Combinatorial Pattern Matching, CPM ’95, held in Espoo, Finland in July 1995.
CPM addresses issues of searching and matching strings and more complicated patterns such as trees, regular expressions, extended expressions, etc. The aim is to derive non-trivial combinatorial properties in order to improve the performance of the corresponding computational problems. This volume presents 27 selected refereed full research papers and two invited papers; it addresses all current aspects of CPM and its applications such as the design and analysis of algorithms for pattern matching problems in strings, graphs, and hypertexts, as well as in biological sequences and molecules.

---

Table of contents :
Computing similarity between RNA strings….Pages 1-16
Of chicken teeth and mouse eyes, or generalized character compatibility….Pages 17-26
Efficient string matching on coded texts….Pages 27-40
Fast approximate matching using suffix trees….Pages 41-54
Common subsequences and supersequences and their expected length….Pages 55-63
Pattern matching in directed graphs….Pages 64-77
Constant-space string matching with smaller number of comparisons: sequential sampling….Pages 78-89
Multi-dimensional pattern matching with dimensional wildcards….Pages 90-101
Minimizing phylogenetic number to find good evolutionary trees….Pages 102-127
Making the shortest-paths approach to sum-of-pairs multiple sequence alignment more space efficient in practice….Pages 128-143
An efficient algorithm for developing topologically valid matchings….Pages 144-161
Polynomial-time algorithm for computing translocation distance between genomes….Pages 162-176
On the complexity of comparing evolutionary trees….Pages 177-190
Suffix cactus: A cross between suffix tree and suffix array….Pages 191-204
Pattern-matching for strings with short descriptions….Pages 205-214
Pairwise alignment with scoring on tuples….Pages 215-229
Matching a set of strings with variable length don’t cares….Pages 230-247
Three-dimensional pattern matching in protein structure analysis….Pages 248-260
Genome analysis: Pattern search in biological macromolecules….Pages 261-285
Matching patterns of an automaton….Pages 286-297
New results and open problems related to non-standard stringology….Pages 298-317
String matching in hypertext….Pages 318-329
Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree….Pages 330-339
A new flexible algorithm for the longest common subsequence problem….Pages 340-351
Smaller representations for finite-state transducers and finite-state automata….Pages 352-365
Multiple sequence comparison: A peptide matching approach….Pages 366-385
On a technique for parsing a string….Pages 386-386
Dictionary look-up with small errors….Pages 387-394
On the editing distance between undirected acyclic graphs and related problems….Pages 395-407