$α$-$β$-Factorization and the Binary Case of Simon's Congruence
This work provides theoretical insights into formal language theory, specifically for researchers studying word factorizations and congruences, but it is incremental as it builds directly on prior factorization methods.
The paper investigates the α-β-factorization of words, characterizing the Simon congruence of k-universal words in terms of 1-universal words and applying these results to binary words to fully characterize the classes and calculate the congruence index.
In 1991 Hébrard introduced a factorization of words that turned out to be a powerful tool for the investigation of a word's scattered factors (also known as (scattered) subwords or subsequences). Based on this, first Karandikar and Schnoebelen introduced the notion of $k$-richness and later on Barker et al. the notion of $k$-universality. In 2022 Fleischmann et al. presented a generalization of the arch factorization by intersecting the arch factorization of a word and its reverse. While the authors merely used this factorization for the investigation of shortest absent scattered factors, in this work we investigate this new $α$-$β$-factorization as such. We characterize the famous Simon congruence of $k$-universal words in terms of $1$-universal words. Moreover, we apply these results to binary words. In this special case, we obtain a full characterization of the classes and calculate the index of the congruence. Lastly, we start investigating the ternary case, present a full list of possibilities for $αβα$-factors, and characterize their congruence.