# α-β-Factorization and the Binary Case of Simon's Congruence

arXiv: https://arxiv.org/abs/2306.14192 · HTML: https://mlsanity.com/paper/2306.14192/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 24 references that are in the map.
- First posted on arXiv 25 Jun 2023.

## Builds on (most cited first, 5 of 5)

- [The height of piecewise-testable languages and the complexity of the logic of subwords](https://mlsanity.com/paper/1511.01807/) (2015)
- [The Edit Distance to k-Subsequence Universality](https://mlsanity.com/paper/2007.09192/) (2020)
- [Efficiently Testing Simon's Congruence](https://mlsanity.com/paper/2005.01112/) (2020)
- [Scattered Factor Universality -- The Power of the Remainder](https://mlsanity.com/paper/2104.09063/) (2021)
- [Absent Subsequences in Words](https://mlsanity.com/paper/2108.13968/) (2021)

## Abstract (arXiv)

In 1991 H'ebrard 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.