Combinatorial Pattern Matching (CPM 2010)

Combinatorial Pattern Matching (CPM) addresses issues of searching and matching strings and more complicated structures such as trees, regular expressions, graphs, point sets, and arrays, in various formats. The goal is to derive non-trivial combinatorial properties of such structures and exploit these properties in order to achieve superior performance for the corresponding computational problems. However, another important goal is to analyze and pinpoint the properties and conditions under which searches cannot be performed efficiently. Over the past few decades a steady flow of high-quality research on this subject has changed a sparse set of isolated results into a full-fledged area of algorithmics. This area is continuing to grow even further due to the increasing demand for speed and efficiency 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 field has produced a large number of excellent new researchers, books, and conferences. One of the first conferences in the area was the Combinatorial Pattern Matching (CPM) conference. The objective of the annual CPM gathering is to provide an international forum for research in combinatorial pattern matching and related applications. The first twenty one meetings were held in Paris, London, Tucson, Padova, Asilomar, Helsinki, Laguna Beach, Aarhus, Piscataway, Warwick, Montreal, Jerusalem, Fukuka, Morelia, Istanbul, Jeju Island, Barcelona, London (Ontario), Pisa, Lille, Brooklyn, and Palermo over the years 1990–2011. After the first meeting, a selection of papers appeared as a special issue of Theoretical Computer Science in volume 92. The proceedings of the third to twenty first meetings appeared in the Springer LNCS series. The general organization and orientation of the CPM conferences is coordinated by a steering committee composed of Alberto Apostolico, Maxime Crochemore, and Zvi Galil. The papers contained in this volume were chosen from the abstracts presented at the 20th Annual Symposium on Combinatorial Pattern Matching, held June 21–23, 2010 at NYU-Poly in Brooklyn, New York. The conference was supported by NYU-Poly, The Center for Advanced Technology in Telecommunication (CATT) and IBM Research. Twenty eight extended abstracts were chosen after a refereeing process, and three presentations were invited to the conference. Those abstracts appeared in the symposium proceedings Springer LNCS 6129. Authors of the seven best ranked conference papers were invited to submit their papers to this special issue of Information and Computation. The papers went through a thorough review and the results appear in this volume.

Authors

• Amihood Amir
• Laxmi Parida

Keywords

No keywords are indexed for this paper.