Combinatorial Pattern Matching

1. Front Matter

   PDF

2. An improved pattern matching algorithm for strings in terms of straight-line programs

   • Masamichi Miyazaki, Ayumi Shinohara, Masayuki Takeda

   Pages 1-11

3. Episode matching

   • Gautam Das, Rudolf Fleischer, Leszek Gasieniec, Dimitris Gunopulos, Juha Kärkkäinen

   Pages 12-27

4. Efficient algorithms for approximate string matching with swaps

   • Jee-Soo Lee, Dong Kyue Kim, Kunsoo Park, Yookun Cho

   Pages 28-39

5. On the complexity of pattern matching for highly compressed two-dimensional texts

   • Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter

   Pages 40-51

6. Estimating the probability of approximate matches

   • Stefan Kurtz, Gene Myers

   Pages 52-64

7. Space- and time-efficient decoding with canonical huffman trees

   • Shmuel T. Klein

   Pages 65-75

8. On weak circular squares in binary words

   • Aviezri S. Fraenkel, Jamie Simpson, Mike Paterson

   Pages 76-82

9. An easy case of sorting by reversals

   • Nicholas Tran

   Pages 83-89

10. External inverse pattern matching

    • Leszek Gasieniec, Piotr Indyk, Piotr Krysta

    Pages 90-101

11. Distributed generation of suffix arrays

    • Gonzalo Navarro, João Paulo Kitajima, Berthier A. Ribeiro-Neto, Nivio Ziviani

    Pages 102-115

12. Direct construction of compact directed acyclic word graphs

    • Maxime Crochemore, Renaud Vérin

    Pages 116-129

13. Approximation algorithms for the fixed-topology phylogenetic number problem

    • Mary Cryan, Leslie Ann Goldberg, Cynthia A. Phillips

    Pages 130-149

14. A new algorithm for the ordered tree inclusion problem

    • Thorsten Richter

    Pages 150-166

15. On incremental computation of transitive closure and greedy alignment

    • Saïd Abdeddaïm

    Pages 167-179

16. Aligning coding DNA in the presence of frame-shift errors

    • Lars Arvestad

    Pages 180-190

17. A filter method for the weighted local similarity search problem

    • Enno Ohlebusch

    Pages 191-205

18. Trie-based data structures for sequence assembly

    • Ting Chen, Steven S. Skiena

    Pages 206-223

19. Flexible identification of structural objects in nucleic acid sequences: Palindromes, mirror repeats, pseudoknots and triple helices

    • Marie-France Sagot, Alain Viari

    Pages 224-246

20. Banishing bias from consensus sequences

    • Amir Ben-Dor, Giuseppe Lancia, R. Ravi, Jennifer Perone

    Pages 247-261

This book constitutes the refereed proceedings of the Eighth Annual Symposium on Combinatorial Pattern Matching, CPM 97, held in Aarhus, Denmark, in June/July 1997.
The volume presents 20 revised full papers carefully selected from 32 submissions received; also included are abstracts of two invited contributions. The volume is devoted to the issue of searching and matching strings and more complicated patterns, such as trees, regular expressions, graphs, point sets and arrays. The results presented are particularly relevant to molecular biology, but also to information retrieval, pattern recognition, compiling, data compression and program analysis.

• combinatorial structures
• data compression
• information retrieval
• molecular biology
• pattern matching
• pattern recognition
• regular expressions
• sets
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics