Skip to main content
SpringerLink
Log in
Book cover

Combinatorial Pattern Matching

19th Annual Symposium, CPM 2008 Pisa, Italy, June 18-20, 2008, Proceedings

  • Conference proceedings
  • © 2008

Overview

Editors:
  1. Paolo Ferragina
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Gad M. Landau
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5029)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: CPM 2008.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (28 papers)

  1. Front Matter

    Download chapter PDF

  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
Back to top

Other volumes

  1. Combinatorial Pattern Matching

Keywords

About this book

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.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation