# Scattered Factor Universality -- The Power of the Remainder

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 31 references that are in the map.
- First posted on arXiv 19 Apr 2021.

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

- [Multivariate Fine-Grained Complexity of Longest Common Subsequence](https://mlsanity.com/paper/1803.00938/) (2018)
- [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)
- [Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering](https://mlsanity.com/paper/1701.07470/) (2017)
- [Languages ordered by the subword order](https://mlsanity.com/paper/1901.02194/) (2019)

## Built on by (most cited first, 2 of 2)

- [m-Nearly k-Universal Words -- Investigating Simon Congruence](https://mlsanity.com/paper/2202.07981/) (2022)
- [α-β-Factorization and the Binary Case of Simon's Congruence](https://mlsanity.com/paper/2306.14192/) (2023)

## Abstract (arXiv)

Scattered factor (circular) universality was firstly introduced by Barker et al. in 2020. A word w is called k-universal for some natural number k, if every word of length k of w's alphabet occurs as a scattered factor in w; it is called circular k-universal if a conjugate of w is k-universal. Here, a word u=u1cdots un is called a scattered factor of w if u is obtained from w by deleting parts of w, i.e. there exists (possibly empty) words v1,dots,vn+1 with w=v1u1v2cdots vnunvn+1. In this work, we prove two problems, left open in the aforementioned paper, namely a generalisation of one of their main theorems to arbitrary alphabets and a slight modification of another theorem such that we characterise the circular universality by the universality. On the way, we present deep insights into the behaviour of the remainder of the so called arch factorisation by Hebrard when repetitions of words are considered.