Combinatorial Pattern Matching

1. Front Matter

   PDF

2. Invited Talks

   1. ReCombinatorics: Combinatorial Algorithms for Studying the History of Recombination in Populations

      • Dan Gusfield

      Pages 1-2

   2. Lower Bounds for Succinct Data Structures

      • J. Ian Munro

      Pages 3-3

   3. The Changing Face of Web Search

      • Prabhakar Raghavan

      Pages 4-4

3. Contributed Papers

   1. Two-Dimensional Pattern Matching with Combined Scaling and Rotation

      • Christian Hundt, Maciej Liśkiewicz

      Pages 5-17

   2. Searching for Gapped Palindromes

      • Roman Kolpakov, Gregory Kucherov

      Pages 18-30

   3. Parameterized Algorithms and Hardness Results for Some Graph Motif Problems

      • Nadja Betzler, Michael R. Fellows, Christian Komusiewicz, Rolf Niedermeier

      Pages 31-43

   4. Finding Largest Well-Predicted Subset of Protein Structure Models

      • Shuai Cheng Li, Dongbo Bu, Jinbo Xu, Ming Li

      Pages 44-55

   5. HP Distance Via Double Cut and Join Distance

      • Anne Bergeron, Julia Mixtacki, Jens Stoye

      Pages 56-68

   6. Fixed Parameter Tractable Alignment of RNA Structures Including Arbitrary Pseudoknots

      • Mathias Möhl, Sebastian Will, Rolf Backofen

      Pages 69-81

   7. Faster Algorithm for the Set Variant of the String Barcoding Problem

      • Leszek Gąsieniec, Cindy Y. Li, Meng Zhang

      Pages 82-94

   8. Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics

      • Tobias Marschall, Sven Rahmann

      Pages 95-106

   9. Analysis of the Size of Antidictionary in DCA

      • Julien Fayolle

      Pages 107-117

   10. Approximate String Matching with Address Bit Errors

       • Amihood Amir, Yonatan Aumann, Oren Kapah, Avivit Levy, Ely Porat

       Pages 118-129

   11. On-Line Approximate String Matching with Bounded Errors

       • Marcos Kiwi, Gonzalo Navarro, Claudio Telha

       Pages 130-142

   12. A Black Box for Online Approximate Pattern Matching

       • Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat

       Pages 143-151

   13. An(other) Entropy-Bounded Compressed Suffix Tree

       • Johannes Fischer, Veli Mäkinen, Gonzalo Navarro

       Pages 152-165

   14. On Compact Representations of All-Pairs-Shortest-Path-Distance Matrices

       • Igor Nitto, Rossano Venturini

       Pages 166-177

   15. Computing Inverse ST in Linear Complexity

       • Ge Nong, Sen Zhang, Wai Hong Chan

       Pages 178-190

   16. Dynamic Fully-Compressed Suffix Trees

       • Luís M. S. Russo, Gonzalo Navarro, Arlindo L. Oliveira

       Pages 191-203

The papers contained in this volume were presented at the 19th Annual S- posium on Combinatorial Pattern Matching (CPM 2008) held at the University of Pisa, Italy, June 18–20, 2008. All the papers presented at the conference are originalresearchcontributions on computational pattern matching and analysis. They were selected from 78 submissions. Each submission was reviewed by at least three reviewers. The committee decided to accept 25 papers. The programme also includes three invited talks by Daniel M. Gus?eld from the University of California, Davis, USA, J. Ian Munro from the University of Waterloo, Canada, and Prabhakar Raghavan from Yahoo! Research, USA. The objective of the annual CPM meetings is to provide an international forum for research in combinatorial pattern matching and related applications. It addresses issues of searching and matching strings and more complicated p- terns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivialcombinatorialproperties of suchstructures and to exploit these properties in order to either achieve superior performance for the cor- sponding computational problems or pinpoint conditions under which searches cannotbeperformede?ciently. Themeeting also dealswith problems incom- tational biology, data compression, data mining, coding, information retrieval, natural language processing and pattern recognition.

• Pattern Matching
• algorithm
• algorithms
• biology
• data compression
• data mining
• databases
• pattern recognition
• algorithm analysis and problem complexity

Policies and ethics