Esko Ukkonen - Böcker

The papers in this volume were presented at SWAT 92, theThird Scandinavian Workshop on Algorithm Theory. Theworkshop, which continues the tradition ofSWAT 88, SWAT 90,and the Workshop on Algorithms and Data Structures (WADS 89,WADS 91), is intended as an international forum forresearchers in the area of design and analysis ofalgorithms. The volume contains invited papers by L. G. Valiant (Direct bulk-synchronous parallel algorithms), A. A. Razborov (On small depth threshold circuits), G. Gonnet(Efficient two-dimensional searching), and E. Welzl (Newresults on linear programming and related problems),together with 34 selected contributed papers. Contributionscover algorithms and data structures in all areas, includingcombinatorics, computational geometry, data bases, paralleland distributed computing, and graphics.

This volume presents the proceedings of the 6th International Symposium on Combinatorial Pattern Matching, CPM '95, held in Espoo, Finland in July 1995.CPM addresses issues of searching and matching strings and more complicated patterns such as trees, regular expressions, extended expressions, etc. The aim is to derive non-trivial combinatorial properties in order to improve the performance of the corresponding computational problems. This volume presents 27 selected refereed full research papers and two invited papers; it addresses all current aspects of CPM and its applications such as the design and analysis of algorithms for pattern matching problems in strings, graphs, and hypertexts, as well as in biological sequences and molecules.

It is our great pleasure to introduce the proceedings of the 20th anniversary edition of the Annual Symposium on Combinatorial Pattern Matching (CPM). The meeting was held in Lille, France,hosted by the Laboratoired'Informatique Fondamentale de Lille (LIFL) a?liated with the Universit' e de Lille 1 and the French Centre National de Recherche Scienti?que (CNRS), as well as by INRIA Lille - Nord Europe. Started in 1990as a summer school with about 30 invited participants, CPM quicklyevolvedintoarepresentativeannualinternationalconference.Principally motivated by combinatorial algorithms for search problems in strings (texts, sequences), the scope of CPM extended to more complex data structures such astrees,graphs,two-dimensionalarrays,or setsof points.Thosestudiesresulted inarichcollectionofalgorithmictechniquesanddatastructures,makingbridges to other parts of the theory of discrete algorithms and algorithm engineering. Today, the area of combinatorial pattern matching is a well-identi?ed active sub?eld of algorithmic research.Importantly, this development has been fertilized by a number of major - plication areas providing direct motivations and fruitful feedback to the CPM problematics. Those applications include data compression, computational bi- ogy,Internetsearch,datamining,informationretrieval,coding,naturallanguage processing,pattern recognition,music analysis, and others. On the one hand, all these areas make use of combinatorial pattern matching techniques and, on the otherhand,raisenewpatternmatchingproblems.Forexample,the fastprogress in computational molecular biology, triggered in the 1990s by the availability of mass genomic data, considerably in?uenced the combinatorial pattern matching ?eld: as an illustration, about one-third of the papers presented in this volume deal with problems related to bioinformatics applications.