# m-Nearly k-Universal Words -- Investigating Simon Congruence

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 29 references that are in the map.
- First posted on arXiv 16 Feb 2022.

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

- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Neural Machine Translation with Byte-Level Subwords](https://mlsanity.com/paper/1909.03341/) (2019)
- [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)
- [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)

Determining the index of the Simon congruence is a long outstanding open problem. Two words u and v are called Simon congruent if they have the same set of scattered factors, which are parts of the word in the correct order but not necessarily consecutive, e.g., mathttoath is a scattered factor of mathttlogarithm. Following the idea of scattered factor k-universality, we investigate m-nearly k-universality, i.e., words where m scattered factors of length k are absent, w.r.t. Simon congruence. We present a full characterisation as well as the index of the congruence for m=1. For mneq 1, we show some results if in addition w is (k-1)-universal as well as some further insights for different m.