Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings

Infinite Sets of Square-Free omega-words Derived from the Prouhet-Thue-Morse Sequence

Erik Jensen
Organization: University of California, Santa Cruz
Veikko Keränen
Organization: Rovaniemi Polytechnic
Department: School of Technology
Klaus Sutner
Organization: Carnegie Mellon University
Department: School of Computer Science

2004 International Mathematica Symposium
Conference location

Banff, Canada

We describe a method to generate an infinite set of unique square-free omega-words from the (Prouhet)-Thue-Morse sequence on a four letter alphabet. This result is a generalization of the method introduced by Axel Thue in 1912 for constructing a square-free omega-word over four (and then over three) letters from the Thue-Morse sequence. The new method has been further generalized to produce infinite sets of square-free omega-words on larger alphabets. We present a method for constructing a new square-free omega-word over three letters from an element of the infinite set of square-free omega-words over six letters that results from the generalization described above.

*Mathematics > Number Theory

Prouhet-Thue-Morse Sequence, Thue-Morse sequence, omega-words
Related items

*New Ideas in Symbolic Computation: Proceedings of the 6th International Mathematica Symposium   [in Books]