×

Combinatorics on words – a tutorial. (English) Zbl 1065.68078

Păun, G. (ed.) et al., Current trends in theoretical computer science. The challenge of the new century. Vol. 2: Formal models and semantics. River Edge, NJ: World Scientific (ISBN 981-238-965-2/hbk; 981-238-783-8/set). 415-475 (2004).
Summary: The goal of this tutorial is to discuss – without aiming to be exhaustive – several typical problems on words, as well as to try to point out several applications. With a few exceptions the proofs are not presented here, however, in some cases we use examples to illustrate the basic ideas. Open problems form an important part of our presentation.
The contents of this tutorial is as follows. At the end of this introductory section we discuss briefly the history of combinatorics on words, and fix some basic terminology. Then in Section 2 we consider connections to other fields of mathematics and computer science. Section 3 is devoted to the most fundamental notion of words, namely to periodicity. Dimension properties of words constitute Section 4, while Section 5 concentrates one of the most studied and most characteristic feature of words, namely unavoidable regularities. Words, indeed, are very suitable objects to formulate such fundamental properties. In Section 6 complexity issues of infinite words are studied from different points of view. An interesting phenomenon is that what is considered to be complicated in a classical sense, e.g., algebraically, need not be so from the point of view of words. Finally, in Section 7 we discuss some extensions of the theory to finite sets of words, and in Section 8 collect a list of important open problems, many of those being apparently very difficult. As we said everywhere above algorithmic and decidability issues are present. We conclude with some bibliographic remarks.
For the entire collection see [Zbl 1048.68048].

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite