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
    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
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    0 references