Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word

DOI10.1007/978-3-319-09698-8_19zbMATH Open1350.68216arXiv1604.02238OpenAlexW2743359144MaRDI QIDQ2921985FDOQ2921985

Authors: Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń 

Publication date: 14 October 2014

Published in: Developments in Language Theory (Search for Journal in Brave)

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 in a word 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 $mathit{SQ}_{mathrmAbel}(n,sigma)$ and $mathitSQ{\text{'}}_{mathrmAbel}(n,sigma)$ denote the maximum number of Abelian squares in a word of length $n$ over an alphabet of size $sigma$, which are distinct as words and which are nonequivalent in the Abelian sense, respectively. For $sigmage2$ we prove that $mathit{SQ}_{mathrmAbel}(n,sigma)=Theta(n^2)$, $mathitSQ{\text{'}}_{mathrmAbel}(n,sigma)=Omega(n^{3/2})$ and $mathitSQ{\text{'}}_{mathrmAbel}(n,sigma)=O(n^{11/6})$. We also give linear bounds for parameterized and order-preserving squares for alphabets of constant size: $mathit{SQ}_{mathrmparam}(n,O(1))=Theta(n)$, $mathit{SQ}_{mathrmop}(n,O(1))=Theta(n)$. The upper bounds have quadratic dependence on the alphabet size for order-preserving squares and exponential dependence for parameterized squares. 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).

Full work available at URL: https://arxiv.org/abs/1604.02238

Recommendations

• Maximum number of distinct and nonequivalent nonstandard squares in a word
• Counting distinct squares in partial words
• Words with the maximum number of abelian squares
• Density of distinct squares in non-primitive words
• A note on the number of squares in a word
• On the number of squares in partial words
• Asymptotic behaviour of the maximal number of squares in standard Sturmian words
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• Extremal square-free words
• Efficient enumeration of non-equivalent squares in partial words with few holes

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cited In (8)

• Constructing words with high distinct square densities
• String powers in trees
• Abelian-square-rich words
• Order-preserving indexing
• Maximum number of distinct and nonequivalent nonstandard squares in a word
• Words with the maximum number of abelian squares
• A note on the number of squares in a word
• String Powers in Trees

This page was built for publication: Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921985)