2025/12/06 by Nguyên, Lê Thành Dũng, Parys, Paweł
Computer Science · #Advanced Graph Theory Research #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Machine Learning and Algorithms #semigroups and automata theory
paper · doi:10.48550/arxiv.2512.06466
openalex publication_date 2025/12/06 · openalex created_date 2025/12/10 · openalex updated_date 2026/07/28
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 × 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.