Combinatorial pattern matching

About this book

The papers contained in this volume were presented at the 14th Annual Sym- sium on Combinatorial Pattern Matching, held June 25–27, 2003 at the Centro Cultural Universitario of the Universidad Michoacana, in Morelia, Michoac´ an, Mexico. They were selected from 57 abstracts submitted in response to the call for papers. In addition, there were invited lectures by Vladimir Levenshtein, from the University of Bergen, Norway, and Ian Munro, from the University of Waterloo, Canada. Combinatorial Pattern Matching (CPM) addresses issues of searching and matching strings and more complicated patterns such as trees, regular expres- ons, graphs, point sets, and arrays, in various formats. The goal is to derive n- trivialcombinatorialpropertiesofsuchstructuresandtoexploittheseproperties in order to achieve superior performance for the corresponding computational problems. Another 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 haschangedasparsesetofisolatedresultsintoafull-?edgedareaofalgorithmics. 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, datacompression,andpatternrecognition.TheobjectiveoftheannualCPM- theringistoprovideaninternationalforumforresearchincombinatorialpattern matching and related applications.