Word

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

A finite sequence of letters from some Alphabet is said to be an -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 , , ab, ba, aba, and bab. However, there are arbitrarily long ternary squarefree words. The number of ternary squarefree words of length 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 of binary overlapfree words of length satisfies

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

(4)

for some constants

and

(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 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.