Berstel, Jean; Karhumäki, Juhani 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]. Cited in 2 Documents MSC: 68R15 Combinatorics on words PDFBibTeX XMLCite \textit{J. Berstel} and \textit{J. Karhumäki}, in: Current trends in theoretical computer science. The challenge of the new century. Vol. 2: Formal models and semantics. River Edge, NJ: World Scientific. 415--475 (2004; Zbl 1065.68078) Online Encyclopedia of Integer Sequences: The infinite Fibonacci word: start with 1, repeatedly apply the morphism 1->12, 2->1, take limit; or, start with S(0)=2, S(1)=1, and for n>1 define S(n)=S(n-1)S(n-2), then the sequence is S(oo). The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit). Thue-Morse sequence: let A_k denote the first 2^k terms; then A_0 = 0 and for k >= 0, A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 0’s and 1’s. If n mod 3 = 0 then a(n) = a(n/3), otherwise a(n) = n mod 3. Tribonacci word: limit S(infinity), where S(0) = 0, S(1) = 0,1, S(2) = 0,1,0,2 and for n >= 0, S(n+3) = S(n+2) S(n+1) S(n). Fixed point of the morphism 0->010, 1->011, starting from a(1) = 0. The ternary tribonacci word; also a Rauzy fractal sequence: fixed point of the morphism 1 -> 12, 2 -> 13, 3 -> 1, starting from a(1) = 1. The Pell word: Fixed point of the morphism 0->001, 1->0.