Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word

Abstract

The combinatorics of squares in a word depends on how the equivalence of halves of the square is defined. We consider Abelian squares, parameterized squares and order-preserving squares. The word $uv$ is an Abelian (parameterized, order-preserving) square if $u$ and $v$ are equivalent in the Abelian (parameterized, order-preserving) sense. The maximum number of ordinary squares is known to be asymptotically linear, but the exact bound is still investigated. We present several results on the maximum number of distinct squares for nonstandard subword equivalence relations. Let $SQAbel(n,k)$ and $SQ'Abel(n,k)$ denote the maximum number of Abelian squares in a word of length n over an alphabet of size k, which are distinct as words and which are nonequivalent in the Abelian sense, respectively. We prove that $SQAbel(n,2)=\Theta(n^2)$ and $SQ'Abel(n,2)=\Omega(n^{1.5}/\log n)$. We also give linear bounds for parameterized and order-preserving squares for small alphabets: $SQ param(n,2)=\Theta(n)$ and $SQ op(n,O(1))=\Theta(n)$. As a side result we construct infinite words over the smallest alphabet which avoid nontrivial order-preserving squares and nontrivial parameterized cubes (nontrivial parameterized squares cannot be avoided in an infinite word).

Publication
Developments in Language Theory 2014:215-226
Date
Type
conference proceedings (see full journal version)