How far are ternary words from shuffle squares?
A shuffle square is a word which consists of two identical and disjoint, but possibly intertwining subwords. For every natural number n, we construct a ternary word of length n which requires a removal of at least Ω(log²n) of its letters in order to become a shuffle square.
Authors
- Andrzej Ruciński (ORCID: https://orcid.org/0000-0002-0742-7694)
- Ayush Basu
Institutions
- Emory University (US)
- Adam Mickiewicz University in Poznań (PL)
Publication Details
- Journal
- Ars Mathematica Contemporanea
- Published
- 2024-12-16
- DOI
- https://doi.org/10.26493/1855-3974.3211.86d
- Citations
- 2
- Primary Topic
- semigroups and automata theory
- Type
- article
- Field-Weighted Citation Impact
- 0.72
Funders
- National Science Foundation
- Narodowe Centrum Nauki