info prev up next book cdrom email home

Word

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.


A finite sequence of $n$ letters from some Alphabet is said to be an $n$-ary word. A ``square'' word consists of two identical subwords (for example, acbacb). A squarefree word contains no square words as subwords (for example, abcacbabcb). The only squarefree binary words are $a$, $b$, ab, ba, aba, and bab. However, there are arbitrarily long ternary squarefree words. The number of ternary squarefree words of length $n$ is bounded by

\begin{displaymath}
6\cdot 1.032^n\leq s(n)\leq 6\cdot 1.379^n
\end{displaymath} (1)

(Brandenburg 1983). In addition,
\begin{displaymath}
S\equiv\lim_{n\to\infty} [s(n)]^{1/n}=1.302\ldots
\end{displaymath} (2)

(Brinkhuis 1983, Noonan and Zeilberger). Binary cubefree words satisfy
\begin{displaymath}
2\cdot 1.080^n\leq c(n)\leq 2\cdot 1.522^n.
\end{displaymath} (3)


A word is said to be overlapfree if it has no subwords of the form xyxyx. A squarefree word is overlapfree, and an overlapfree word is cubefree. The number $t(n)$ of binary overlapfree words of length $n$ satisfies

\begin{displaymath}
p\cdot n^{1.155}\leq t(n)\leq q \cdot n^{1.587}
\end{displaymath} (4)

for some constants $p$ and $q$ (Restivo and Selemi 1985, Kobayashi 1988). In addition, while
\begin{displaymath}
\lim_{n\to\infty} {\ln t(n)\over \ln n}
\end{displaymath} (5)

does not exist,
\begin{displaymath}
1.155<T_L<1.276<1.332<T_U<1.587,
\end{displaymath} (6)

where
$\displaystyle T_L$ $\textstyle \equiv$ $\displaystyle \liminf_{n\to\infty} {\ln t(n)\over\ln n}$ (7)
$\displaystyle T_U$ $\textstyle \equiv$ $\displaystyle \limsup_{n\to\infty} {\ln t(n)\over\ln n}$ (8)

(Cassaigne 1993).

See also Alphabet


References

Brandenburg, F.-J. ``Uniformly Growing $k$th Power-Free Homomorphisms.'' Theor. Comput. Sci. 23, 69-82, 1983.

Brinkhuis, J. ``Non-Repetitive Sequences on Three Symbols.'' Quart. J. Math. Oxford Ser. 2 34, 145-149, 1983.

Cassaigne, J. ``Counting Overlap-Free Binary Words.'' STACS '93: Tenth Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993 Proceedings (Ed. G. Goos, J. Hartmanis, A. Finkel, P. Enjalbert, K. W. Wagner). New York: Springer-Verlag, pp. 216-225, 1993.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/words/words.html

Kobayashi, Y. ``Enumeration of Irreducible Binary Words.'' Discrete Appl. Math. 20, 221-232, 1988.

Noonan, J. and Zeilberger, D. ``The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations.'' Submitted.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26