Prague Stringology Conference 2026
Hiroki Shibata, Takuya Mieno, Dominik Köppl and Shunsuke Inenaga
Relaxation of Square-Freeness
| Abstract: |
| We extend the analysis of nonrepetitive sequences of Entringer et al. [Journal of Combinatorial Theory, 1974] to relaxations of equality testing under nonstandard equivalence relations, in particular parameterized equivalence and order-preserving equivalence. For this setting, we introduce l+-squares, defined as squares whose total length is at least 2l. We obtain an infinite 3+-parameterized-square-free ternary word and an infinite 3+-order-preserving-square-free binary word through an approach based on combinatorics on words. In addition, we report the longest l+-square-free words across several equivalence relations. |
| Download paper: |  |
 |
|
| BibTeX reference |