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 ${\ell }^{+}$-squares, defined as squares whose total length is at least $2\ell$. 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 ${\ell }^{+}$-square-free words across several equivalence relations.

Accepted for PSC 2026