The papers contained in this volume were presented at the 13th Annual S- posium on Combinatorial Pattern Matching, held July 3–5, 2002 at the Hotel Uminonakamichi, in Fukuoka, Japan. They were selected from 37 abstracts s- mitted in response to the call for papers. In addition, there were invited lectures by Shinichi Morishita (University of Tokyo) and Hiroki Arimura (Kyushu U- versity). Combinatorial Pattern Matching (CPM) addresses issues of searching and matching strings and more complicated patterns such as trees, regular expr- sions, graphs, point sets, and arrays, in various formats. The goal is to derive n- trivial combinatorial properties of such structures and to exploit these properties in order to achieve superior performance for the corresponding computational problems. On the other hand, an important goal is to analyze and pinpoint the properties and conditions under which searches cannot be performed e?ciently. Over the past decade a steady ?ow of high-quality research on this subject has changed a sparse set of isolated results into a full-?edged area of algorithmics. This area is continuing to grow even further due to the increasing demand for speed and e?ciency that stems from important applications such as the World Wide Web, computational biology, computer vision, and multimedia systems. These involve requirements for information retrieval in heterogeneous databases, data compression, and pattern recognition. The objective of the annual CPM gathering is to provide an international forum for research in combinatorial p- tern matching and related applications.
Author(s): Jun Ogasawara, Shinichi Morishita (auth.), Alberto Apostolico, Masayuki Takeda (eds.)
Series: Lecture Notes in Computer Science 2373
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2002
Language: English
Pages: 290
Tags: Algorithm Analysis and Problem Complexity; Pattern Recognition; Document Preparation and Text Processing; Information Storage and Retrieval; Coding and Information Theory; Discrete Mathematics in Computer Science
Practical Software for Aligning ESTs to Human Genome....Pages 1-16
Efficient Text Mining with Optimized Pattern Discovery....Pages 17-19
Application of Lempel-Ziv Factorization to the Approximation of Grammar-Based Compression....Pages 20-31
Block Merging for Off-Line Compression....Pages 32-41
String Matching with Stopper Encoding and Code Splitting....Pages 42-52
Pattern Matching Problems over 2-Interval Sets....Pages 53-63
The Problem of Context Sensitive String Matching....Pages 64-75
Two-Pattern Strings....Pages 76-84
Edit Distance with Move Operations....Pages 85-98
Towards Optimally Solving the Longest Common Subsequence Problem for Sequences with Nested Arc Annotations in Linear Time....Pages 99-114
Local Similarity Based Point-Pattern Matching....Pages 115-132
Identifying Occurrences of Maximal Pairs in Multiple Strings....Pages 133-143
Space-Economical Algorithms for Finding Maximal Unique Matches....Pages 144-152
The Minimum DAWG for All Suffixes of a String and Its Applications....Pages 153-167
On the Complexity of Deriving Position Specific Score Matrices from Examples....Pages 168-177
Three Heuristics for δ-Matching: δ-BM Algorithms....Pages 178-189
A Better Method for Length Distribution Modeling in HMMs and Its Application to Gene Finding....Pages 190-202
Faster Bit-Parallel Approximate String Matching....Pages 203-224
One-Gapped q-Gram Filters for Levenshtein Distance....Pages 225-234
Optimal Exact and Fast Approximate Two Dimensional Pattern Matching Allowing Rotations....Pages 235-248
Statistical Identification of Uniformly Mutated Segments within Repeats....Pages 249-261
Simple and Practical Sequence Nearest Neighbors with Block Operations....Pages 262-278
Constructing NFAs by Optimal Use of Positions in Regular Expressions....Pages 279-288
