Some recent results on squarefree words. (English) Zbl 0582.68042

Theoretical aspects of computer science, Symp., Paris 1984, Lect. Notes Comput. Sci. 166, 14-25 (1984).
[For the entire collection see Zbl 0533.00025.]
This paper is a survey of results on square-free words which contains numerous references to the literature, where the original results and their proofs can be found. Topics covered include the existence of square-face words, the complexity of algorithms to find all repetitions of a word of length n \((=O(n \log n))\), bounds on the number of square- free words of a given length over a fixed alphabet, and square-free morphisms of languages. Several open problems are mentioned.
Reviewer: W.R.Nico


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity




Zbl 0533.00025