A finer reparameterisation theorem for MSO and FO queries on strings
By: Lê Thành Dũng Nguyên, Paweł Parys
Potential Business Impact:
Finds patterns in text faster.
We show a theorem on monadic second-order k-ary queries on finite words. It may be illustrated by the following example: if the number of results of a query on binary strings is O(number of 0s $\times$ number of 1s), then each result can be MSO-definably identified from a 0-position, a 1-position and some finite data. Our proofs also handle the case of first-order logic / aperiodic monoids. Thus we can state and prove the folklore theorem that dimension minimisation holds for first-order string-to-string interpretations.
Similar Papers
Multidimensional tilings and MSO logic
Formal Languages and Automata Theory
Makes computer patterns follow simple rules.
On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers
Data Structures and Algorithms
Finds solutions by moving pieces on a board.
On Expansions of Monadic Second-Order Logic with Dynamical Predicates
Logic in Computer Science
Lets computers check number patterns automatically.