The papers contained in this volume were presented at the Fourth Annual Symposium on Combinatorial Pattern Matching, held in Padova, Italy, in June 1993. Combinatorial pattern matching addresses issues of searching and matching of strings and more complicated patterns such as trees, regular expressions, extended expressions, etc. The goal is to derive nontrivial combinatorial properties for such structures and then to exploit these properties in order to achieve superior performance for the corresponding computational problems. In recent years, a steady flow of high-quality scientific studies of this subject has changed a sparse set of isolated results into a full-fledged area of algorithmics. The area is expected to grow even further due to the increasing demand for speedand efficiency that comes especially from molecular biology and the Genome project, but also from other diverse areas such as information retrieval, pattern recognition, compilers, data compression, and program analysis.

This volume contains the 22 papers accepted for presentation at the Third Annual Symposium on Combinatorial Pattern Matching held April 29 to May 1, 1992, in Tucson, Arizona; it constitutes the first conference proceedings entirely devoted to combinatorial pattern matching (CPM). CPM deals withissues of searching and matching of strings and other more complicated patterns such as trees, regular expressions, extended expressions, etc. in order to derive combinatorial properties for such structures. As an interdisciplinary field of growing interest, CPM is related to research in information retrieval, pattern recognition, compilers, data compression, and program analysis as well as to results, problems and methods from combinatorial mathematics and molecular biology.

Introduction. Historical Overview. Databases: Office Information Systems Engineering (J. Palazzo, D. Alcoba) Artificial Intelligence, Logic, and Functional Programming: A HyperIcon Interface to a Blackboard System for Planning Research Projects (P. Charlton, C. Burdorf). Algorithms and Data Structures: Classification of Quadratic Algorithms for Multiplying Polynomials of Small Degree Over Finite Fields (A. Averbuch et al.). Object Oriented Systems: A Graphical Interactive Object Oriented Development System (M. Adar et al.). Distributed Systems: Preserving Distributed Data Coherence Using Asynchronous Broadcasts (J. Piquer). Complexity and Parallel Algorithms: Parallel Algorithms for NPComplete Problems (M. Robson). Computer Architecture and Networks: The Caracas Multiprocessor System (M. Campo et al.). 30 additional articles. Index.