# zbMATH — the first resource for mathematics

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

##### MSC:
 68Q45 Formal languages and automata 68Q25 Analysis of algorithms and problem complexity
survey