Binary words avoided by the Thue-Morse sequence (Q1924519)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Binary words avoided by the Thue-Morse sequence |
scientific article |
Statements
Binary words avoided by the Thue-Morse sequence (English)
0 references
16 March 1997
0 references
Let \(A=\{a,b\}\), \(\Sigma=\{x,y\}\) be binary alphabets, \(A^+\), \(\Sigma^+\) the corresponding free semigroups. A word \(W\) avoids a word \(U\) (resp. \(U\) is avoided by \(W\)), if \(W\) does not have subwords which are homomorphic images of the word \(U\). The sequences \(U_n=\phi_n(a)\), \(V_n=\phi_n(ba)\) of Thue-Morse words \(U_n\), \(V_n\) are defined by the endomorphism \(\phi\) of \(A^+\): \(\phi(a)=ab\), \(\phi(b)=ba\). Define sequences \(S_k\), \(T_m\) of words in \(\Sigma^+\) by \(S_k=1(\phi^k(x))\phi^k(x)\phi^k(y)\phi^k(x)0(\phi^k(x))\), \(T_m=1(\phi^m(x))\phi^m(y)\phi^m(x)\phi^m(y)0(\phi^m(x))\), where \(0(W)\), \(1(W)\) denote the first and the last symbol of a word \(W\). The main theorem: The collection of binary words avoided by the Thue-Morse sequence is the fully invariant ideal of the semigroup \(\Sigma^+\), generated by the set \(\{xxx,xyxyx,xxyxxy,xyyxyy,\;S_{k}\) \((k\geq 1),\;T_m\) \((m\geq 2)\}\).
0 references
avoided words
0 references
Thue-Morse sequences
0 references
binary alphabets
0 references
free semigroups
0 references
Thue-Morse words
0 references
binary words
0 references