Ferdinando Cicalese Books

This book constitutes the refereed proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015, held on Ischia Island, Italy, in June/July 2015. The 34 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 83 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees; regular expressions; graphs; point sets; and arrays. The goal is to derive combinatorial properties of such structures and to exploit these properties in order to achieve superior performance for the corresponding computational problems. The meeting also deals with problems in computational biology; data compression and data mining; coding; information retrieval; natural language processing; and pattern recognition.

Searching is a fundamental problem in computer science, with algorithmic and combinatorial issues finding applications across various areas. Fault-tolerance is crucial in computing due to the inherent complexity of information systems, which are prone to errors at multiple levels, including data imprecisions, software bugs, and hardware failures. This book offers a concise and rigorous exploration of fault-tolerance within algorithmic search theory. It begins with the Ulam—Rényi problem, presenting a model for fault-tolerant search and guiding readers through increasingly complex variants. Key combinatorial and algorithmic challenges in designing fault-tolerant search procedures are examined, focusing on the algorithmic efficiency relative to the statistical nature of error sources and the information available to the search algorithm. The second part delves into broader fault models and fault-tolerance applications, emphasizing their relevance in distributed computing, bioinformatics, and computational learning. This work is particularly valuable for researchers in combinatorial search and fault-tolerant computation, as well as those in learning theory, databases, and artificial intelligence. It requires only a basic understanding of discrete mathematics and can serve as a foundation for specialized graduate courses on combinatorial search or as supplementary material for courses on error-correcting codes.