Combinatorial Pattern Matching: Third Annual Symposium Tucson, Arizona, USA, April 29–May 1, 1992 Proceedings

Wojciech Szpankowski (auth.), Alberto Apostolico, Maxime Crochemore, Zvi Galil, Udi Manber (eds.)3540560246, 9783540560241

This volume contains the 22 papers accepted for presentation at the Third Annual Symposium on Combinatorial Pattern Matching held April 29 to May 1, 1992, in Tucson, Arizona; it constitutes the first conference proceedings entirely devoted to combinatorial pattern matching (CPM). CPM deals withissues of searching and matching of strings and other more complicated patterns such as trees, regular expressions, extended expressions, etc. in order to derive combinatorial properties for such structures. As an interdisciplinary field of growing interest, CPM is related to research in information retrieval, pattern recognition, compilers, data compression, and program analysis as well as to results, problems and methods from combinatorial mathematics and molecular biology.

---

Table of contents :
Probabilistic analysis of generalized suffix trees….Pages 1-14
A language approach to string searching evaluation….Pages 15-26
Pattern matching with mismatches: A probabilistic analysis and a randomized algorithm….Pages 27-40
Fast multiple keyword searching….Pages 41-51
Heaviest increasing/common subsequence problems….Pages 52-66
Approximate regular expression pattern matching with concave gap penalties….Pages 67-78
Matrix longest common subsequence problem, duality and hilbert bases….Pages 79-89
From regular expressions to DFA’s using compressed NFA’s….Pages 90-110
Identifying periodic occurrences of a template with applications to protein structure….Pages 111-120
Edit distance for genome comparison based on non-local operations….Pages 121-135
3-D substructure matching in protein Molecules….Pages 136-150
Fast serial and parallel algorithms for approximate tree matching with VLDC’s (Extended Abstract)….Pages 151-161
Grammatical tree matching….Pages 162-174
Theoretical and empirical comparisons of approximate string matching algorithms….Pages 175-184
Fast and practical approximate string matching….Pages 185-192
DZ A text compression algorithm for natural languages….Pages 193-204
Multiple alignment with guaranteed error bounds and communication cost….Pages 205-213
Two algorithms for the longest common subsequence of three (or more) strings….Pages 214-229
Color Set Size problem with applications to string matching….Pages 230-243
Computing display conflicts in string and circular string visualization….Pages 244-261
Efficient randomized dictionary matching algorithms….Pages 262-275
Dynamic dictionary matching with failure functions….Pages 276-287