Morphic word

You can help expand this article with text translated from the corresponding article in French. (June 2021) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must follow the LLM translation guideline, revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Consider adding a topic to this template: there are already 1,423 articles in the main category, and specifying|topic= will aid in categorization. Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article. You must provide copyright attribution in the edit summary accompanying your translation by providing an interlanguage link to the source of your translation. A model attribution edit summary is Content in this edit is translated from the existing French Wikipedia article at [[:fr:Mot morphique]]; see its history for attribution. You may also add the template {{Translated|fr|Mot morphique}} to the talk page. For more guidance, see Wikipedia:Translation.

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.

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 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. 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.

Examples

• The Thue–Morse sequence is generated over {0,1} by the 2-uniform endomorphism 0 → 01, 1 → 10.
• The Fibonacci word is generated over {a,b} by the endomorphism a → ab, b → a.
• 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.

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.

See also

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

References

• 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 (eds.). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 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. Vol. 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. Vol. 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 (5): 497–510. doi:10.1006/eujc.1996.0110. Zbl 0881.68065.