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

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.