Combinatorial Pattern Matching: Third Annual Symposium, Tucson, Arizona, USA, April 29-May 1, 1992 : Proceedings"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."--PUBLISHER'S WEBSITE. |
From inside the book
Results 1-3 of 88
Page 54
... Sequences and Subsequences ... Let σ0102 · Op be a sequence over some alphabet A. We shall use σ ; to denote the ith symbol of σ , and σ ; ... ; to denote the contiguous subsequence consisting of symbols in positions from i to j . A ...
... Sequences and Subsequences ... Let σ0102 · Op be a sequence over some alphabet A. We shall use σ ; to denote the ith symbol of σ , and σ ; ... ; to denote the contiguous subsequence consisting of symbols in positions from i to j . A ...
Page 67
... sequence and one of the sequences specified by the pattern . An alignment is simply a pairing of symbols between two sequences , A = a1a2 ... aм and B = b1b2 ... by over alphabet Σ , such that the lines of the induced trace do not cross ...
... sequence and one of the sequences specified by the pattern . An alignment is simply a pairing of symbols between two sequences , A = a1a2 ... aм and B = b1b2 ... by over alphabet Σ , such that the lines of the induced trace do not cross ...
Page 205
... sequences are not quite adequate ; thus , for practical sequence alignment it is not always necessary to produce an optimal alignment but only one that is plausible . The Gusfield [ 5 ] approximation algorithm produces plausible ...
... sequences are not quite adequate ; thus , for practical sequence alignment it is not always necessary to produce an optimal alignment but only one that is plausible . The Gusfield [ 5 ] approximation algorithm produces plausible ...
Contents
A Language Approach to String Searching Evaluation | 15 |
Fast Multiple Keyword Searching | 41 |
Approximate Regular Expression Pattern Matching with | 67 |
Copyright | |
9 other sections not shown
Other editions - View all
Common terms and phrases
alphabet approximate string matching arithmetic coding atoms automaton b-suffix bound C₁ candidate character circular strings CNNFA compact suffix tree comparison complexity Computer Science construction corresponding data compression data structure de(v defined deletion denote diagonal dictionary matching displayable entities dynamic programming edit distance efficient Euler Tour extension edge function Galil genes genomes given graph hashing I-forest implemented input strings insertion integer label leaf Lemma length longest common subsequence matching algorithm matching problem matrix McNaughton and Yamada's method Mm,n molecule motif multiple alignment MYNNFA n-gram NNFA node noncompact suffix trees nonperiodic O(kn O(log occurs operations optimal pair parse path pattern matching position prefix preprocessing probability Proof proteins random regular expression represents root running score sequence solve space substring subtree suffix tree symbol Theorem tree inclusion tree pattern matching trie values vertex Vishkin weight Yamada's NFA