Maximum number of distinct and nonequivalent nonstandard squares in a word

详细信息    查看全文

• 作者：Tomasz Kociumaka ^{kociumaka@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Jakub Radoszewski ; ^{jrad@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Wojciech Rytter ^{rytter@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Tomasz Waleń ^{walen@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Abelian squares ; Parameterized squares ; Order-preserving squares
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 October 2016
• 年：2016
• 卷：648
• 期：Complete
• 页码：84-95
• 全文大小：422 K

文摘

The combinatorics of nonstandard 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 factor equivalence relations. Let 65b0f700a1589c" title="Click to view the MathML source">SQ_Abel(n,σ)${\mathit{SQ}}_{\mathrm{Abel}}(n,\sigma )$ and ${\mathit{SQ}}_{\mathrm{Abel}}^{\prime }(n,\sigma )$ denote the maximum number of Abelian squares in a word of length n over an alphabet of size σ   which are distinct as words and which are nonequivalent in the Abelian sense, respectively. For σ≥2$\sigma \ge 2$ we prove that SQ_Abel(n,σ)=Θ(n²)${\mathit{SQ}}_{\mathrm{Abel}}(n,\sigma )=\mathrm{\Theta }(n^2)$, ${\mathit{SQ}}_{\mathrm{Abel}}^{\prime }(n,\sigma )=\mathrm{\Omega }(n^{3/2})$ and ${\mathit{SQ}}_{\mathrm{Abel}}^{\prime }(n,\sigma )=O(n^{11/6})$. We also give linear bounds for parameterized and order-preserving squares for alphabets of constant size: SQ_param(n,O(1))=Θ(n)${\mathit{SQ}}_{\mathrm{param}}(n,O(1))=\mathrm{\Theta }(n)$, b0532" title="Click to view the MathML source">SQ_op(n,O(1))=Θ(n)${\mathit{SQ}}_{\mathrm{op}}(n,O(1))=\mathrm{\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). A preliminary version of this paper was published at DLT 2014 [24]. In this full version we improve or extend the bounds on all three kinds of squares.