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.
Author(s): Wojciech Szpankowski (auth.), Alberto Apostolico, Maxime Crochemore, Zvi Galil, Udi Manber (eds.)
Series: Lecture Notes in Computer Science 644
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1992
Language: English
Pages: 293
Tags: Algorithm Analysis and Problem Complexity; Pattern Recognition; Document Preparation and Text Processing; Information Storage and Retrieval; Coding and Information Theory; Combinatorics
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
