Name
Abstract | ||
|---|---|---|
An abelian square is the concatenation of two words that are anagrams of one another. A word of length $n$ can contain at most $\Theta(n^2)$ distinct factors, and there exist words of length $n$ containing $\Theta(n^2)$ distinct abelian-square factors, that is, distinct factors that are abelian squares. This motivates us to study infinite words such that the number of distinct abelian-square factors of length $n$ grows quadratically with $n$. More precisely, we say that an infinite word $w$ is {\it abelian-square-rich} if, for every $n$, every factor of $w$ of length $n$ contains, on average, a number of distinct abelian-square factors that is quadratic in $n$; and {\it uniformly abelian-square-rich} if every factor of $w$ contains a number of distinct abelian-square factors that is proportional to the square of its length. Of course, if a word is uniformly abelian-square-rich, then it is abelian-square-rich, but we show that the converse is not true in general. We prove that the Thue-Morse word is uniformly abelian-square-rich and that the function counting the number of distinct abelian-square factors of length $2n$ of the Thue-Morse word is $2$-regular. As for Sturmian words, we prove that a Sturmian word $s_{\alpha}$ of angle $\alpha$ is uniformly abelian-square-rich if and only if the irrational $\alpha$ has bounded partial quotients, that is, if and only if $s_{\alpha}$ has bounded exponent. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.tcs.2017.02.012 | Theor. Comput. Sci. |
DocType | Volume | Citations |
Journal | 684 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gabriele Fici | 1 | 252 | 30.13 |
| Filippo Mignosi | 2 | 569 | 99.71 |
| Jeffrey Shallit | 3 | 45 | 17.47 |