Morphic word

In mathematics and computer science, a morphic word or substitutive word is an infinite sequence of symbols which is constructed from a particular class of endomorphism of a free monoid.

Every automatic sequence is morphic.^[1]

Definition

Let f be an endomorphism of the free monoid A^∗ on an alphabet A with the property that there is a letter a such that f(a) = as for a non-empty string s: we say that f is prolongable at a. The word

$a s f(s) f(f(s)) \cdots f^{(n)}(s) \cdots \$

is a pure morphic or pure substitutive word. It is clearly a fixed point of the endomorphism f: the unique such sequence beginning with the letter a.^[2][3] In general, a morphic word is the image of a pure morphic word under a coding.^[1]

If a morphic word is constructed as the fixed point of a prolongable k-uniform morphism on A^∗ then the word is k-automatic. The n-th term in such a sequence can be produced by a finite state automaton reading the digits of n in base k.^[1]

Examples

• The Thue–Morse sequence is generated over {0,1} by the 2-uniform endomorphism 0 → 01, 1 → 10.^[4][5]
• The Fibonacci word is generated over {a,b} by the endomorphism a → ab, b → a.^[1][4]
• The tribonacci word is generated over {a,b,c} by the endomorphism a → ab, b → ac, c → a.^[5]
• The Rudin–Shapiro sequence is obtained from the fixed point of the 2-uniform morphism a → ab, b → ac, c → db, d → dc followed by the coding a,b → 0, c,d → 1.^[5]
• The regular paperfolding sequence is obtained from the fixed point of the 2-uniform morphism a → ab, b → cb, c → ad, d → cd followed by the coding a,b → 0, c,d → 1.^[6]

D0L system

A D0L system (deterministic context-free Lindenmayer system) is given by a word w of the free monoid A^∗ on an alphabet A together with a morphism σ prolongable at w. The system generates the infinite D0L word ω = lim_n→∞ σⁿ(w). Purely morphic words are D0L words but not conversely. However if ω = uν is an infinite D0L word with an initial segment u of length |u| ≥ |w|, then zν is a purely morphic word, where z is a letter not in A.^[7]

References

1. Lothaire (2005) p.524
2. Lothaire (2011) p. 10
3. Honkala (2010) p.505
4. Lothaire (2011) p. 11
5. Lothaire (2005) p.525
6. Lothaire (2005) p.526
7. Honalka (2010) p.506

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Honkala, Juha (2010). "The equality problem for purely substitutive words". In Berthé, Valérie; Rigo, Michel. Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications 135. Cambridge: Cambridge University Press. pp. 505–529. ISBN 978-0-521-51597-9. Zbl 1216.68209.
• Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 0-521-84802-4. Zbl 1133.68067.
• Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.

Further reading

• Cassaigne, Julien; Karhumäki, Juhani (1997). "Toeplitz words, generalized periodicity and periodically iterated morphisms". European Journal of Combinatorics 18: 497–510. doi:10.1006/eujc.1996.0110. Zbl 0881.68065.