Combinatorial Pattern Matching

1. Front Matter

   Pages I-VIII

   PDF

2. Practical Software for Aligning ESTs to Human Genome

   • Jun Ogasawara, Shinichi Morishita

   Pages 1-16

3. Efficient Text Mining with Optimized Pattern Discovery

   • Hiroki Arimura

   Pages 17-19

4. Application of Lempel-Ziv Factorization to the Approximation of Grammar-Based Compression

   • Wojciech Rytter

   Pages 20-31

5. Block Merging for Off-Line Compression

   • Raymond Wan, Alistair Moffat

   Pages 32-41

6. String Matching with Stopper Encoding and Code Splitting

   • Jussi Rautio, Jani Tanninen, Jorma Tarhio

   Pages 42-52

7. Pattern Matching Problems over 2-Interval Sets

   • Stéphane Vialette

   Pages 53-63

8. The Problem of Context Sensitive String Matching

   • Venkatesan T. Chakaravarthy, Rajasekar Krishnamurthy

   Pages 64-75

9. Two-Pattern Strings

   • František Franěk, Jiandong Jiang, Weilin Lu, William F. Smyth

   Pages 76-84

10. Edit Distance with Move Operations

    • Dana Shapira, James A. Storer

    Pages 85-98

11. Towards Optimally Solving the Longest Common SubsequenceProblem for Sequences with Nested Arc Annotations in Linear Time

    • Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier

    Pages 99-114

12. Local Similarity Based Point-Pattern Matching

    • Veli Mäkinen, Esko Ukkonen

    Pages 115-132

13. Identifying Occurrences of Maximal Pairs in Multiple Strings

    • Costas S. Iliopoulos, Christos Makris, Spiros Sioutas, Athanasios Tsakalidis, Kostas Tsichlas

    Pages 133-143

14. Space-Economical Algorithms for Finding Maximal Unique Matches

    • Wing-Kai Hon, Kunihiko Sadakane

    Pages 144-152

15. The Minimum DAWG for All Suffixes of a String and Its Applications

    • Shunsuke Inenaga, Masayuki Takeda, Ayumi Shinohara, Hiromasa Hoshino, Setsuo Arikawa

    Pages 153-167

16. On the Complexity of Deriving Position Specific Score Matrices from Examples

    • Tatsuya Akutsu, Hideo Bannai, Satoru Miyano, Sascha Ott

    Pages 168-177

17. Three Heuristics for δ-Matching: δ-BM Algorithms

    • Maxime Crochemore, Costas S. Iliopoulos, Thierry Lecroq, Wojciech Plandowski, Wojciech Rytter

    Pages 178-189

18. A Better Method for Length Distribution Modeling in HMMs and Its Application to Gene Finding

    • Broňa Brejová, Tomáš Vinař

    Pages 190-202

19. Faster Bit-Parallel Approximate String Matching

    • Heikki Hyyrö, Gonzalo Navarro

    Pages 203-224

20. One-Gapped q-Gram Filters for Levenshtein Distance

    • Stefan Burkhardt, Juha Kärkkäinen

    Pages 225-234

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.

• Graph
• Matching
• computer
• data compression
• information
• multimedia
• pattern recognition
• regular expressions
• algorithm analysis and problem complexity

• Department of Electrial Engineering and Computer Science, University of Padova, Padova, Italy

  Alberto Apostolico

• Department of Informatics, Kyushu University, Japan

  Masayuki Takeda

Policies and ethics