CPM 2022

33rd Annual Symposium on Combinatorial Pattern Matching

Prague, Czech Republic, June 27–29, 2022

Keynote speakers

Takehiro Ito

Tohoku University, Japan

Invitation to Combinatorial Reconfiguration

Combinatorial reconfiguration studies reachability and related questions over the solution space formed by feasible solutions of an instance of a combinatorial search problem. For example, as the solution space for the satisfiability problem, we may consider the subgraph of the hypercube induced by the satisfying truth assignments of a given CNF formula. Then, the reachability problem for the satisfiability problem is to ask whether two given satisfying truth assignments are contained in the same connected component of the solution space. The study of reconfiguration problems has motivation from a variety of fields such as puzzles, statistical physics, and industry. In this decade, reconfiguration problems have been studied intensively for many central combinatorial search problems, such as the satisfiability problem, the independent set problem and the coloring problem, from the algorithmic viewpoints. Many reconfiguration problems are PSPACE-complete in general, although several efficiently solvable cases have been obtained. In this talk, I will give a broad introduction of combinatorial reconfiguration.

Jeffrey Shallit

University of Waterloo, Canada

Using automata and a decision procedure to prove results in pattern matching

Many classical infinite words, such as the Thue-Morse word and the Fibonacci word, arise as examples in combinatorics on words and combinatorial pattern matching. Proving properties of such words often involves detailed case analysis. In this article I will show how, in many cases, interesting properties can be proved “purely mechanically”, using a decision procedure. I will illustrate the ideas using the notion of string attractors, recently introduced by Kempa and Prezza. This is joint work with Luke Schaeffer.

Sharma V. Thankachan

University of Central Florida, USA

Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-isomorphic, 2D, etc.

In the past two decades, we have witnessed the design of various compact data structures for pattern matching over an indexed text. Popular indexes like the FM-index, compressed suffix arrays/trees, the recent r-index, etc., capture the key functionalities of classic suffix arrays/trees in compact space. Mostly, they rely on the Burrows-Wheeler Transform (BWT) and its associated operations. However, compactly encoding some advanced suffix tree (ST) variants, like parameterized ST, order-isomorphic/preserving ST, two-dimensional ST, etc.- collectively known as suffix trees with missing suffix links, has been challenging. The previous techniques are not easily extendable because these variants do not hold some structural properties of the standard ST that enable compression. Only recently, we have made some limited progress in these directions. This talk will briefly survey them and highlight some interesting open problems along these lines.