Morphic word#D0L system

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))\; \backslash cdots\; f^\{(n)\}(s)\; \backslash cdots\; \backslash$

is a pure morphic or pure substitutive word. Note that it is the limit of the sequence a, f(a), f(f(a)), f(f(f(a))), ...

It is clearly a fixed point of the endomorphism f: the unique such sequence beginning with the letter a.Lothaire (2011) p. 10Honkala (2010) p.505 In general, a morphic word is the image of a pure morphic word under a coding, that is, a morphism that maps letter to letter.

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.

• The Thue–Morse sequence is generated over {0,1} by the 2-uniform endomorphism 0 → 01, 1 → 10.Lothaire (2011) p. 11Lothaire (2005) p.525
• The Fibonacci word is generated over {a,b} by the endomorphism a → ab, b → a.Lothaire (2005) p.524
• The tribonacci word is generated over {a,b,c} by the endomorphism a → ab, b → ac, c → a.
• 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.
• 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.Lothaire (2005) p.526

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.Honkala (2010) p.506

• Cutting sequence
• Lyndon word
• Hall word
• Sturmian word

{{reflist}}

• {{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = Cambridge University Press | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}
• {{cite book | editor1-last=Berthé | editor1-first=Valérie|editor-link= Valérie Berthé | editor2-last=Rigo | editor2-first=Michel | title=Combinatorics, automata, and number theory | series=Encyclopedia of Mathematics and its Applications | volume=135 | location=Cambridge | publisher=Cambridge University Press | year=2010 | isbn=978-0-521-51597-9 | zbl=1216.68209 | last=Honkala | first=Juha | chapter=The equality problem for purely substitutive words| pages=505–529 }}
• {{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Applied combinatorics on words | others=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é | series=Encyclopedia of Mathematics and Its Applications | volume=105 | location=Cambridge | publisher=Cambridge University Press | year=2005 | isbn=0-521-84802-4 | zbl=1133.68067 | url-access=registration | url=https://archive.org/details/appliedcombinato0000loth }}
• {{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Algebraic combinatorics on words | others=With preface by Jean Berstel and Dominique Perrin | edition=Reprint of the 2002 hardback | series=Encyclopedia of Mathematics and Its Applications | volume=90| publisher=Cambridge University Press | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}

• {{cite journal | last1=Cassaigne | first1=Julien | last2=Karhumäki | first2=Juhani | title=Toeplitz words, generalized periodicity and periodically iterated morphisms | zbl=0881.68065 | journal=European Journal of Combinatorics | volume=18 | pages=497–510 | year=1997 | issue=5 | doi=10.1006/eujc.1996.0110| doi-access=free }}

Category:Semigroup theory

Category:Formal languages

Category:Combinatorics on words