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.

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 = 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, f, f,...
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 by the 2-uniform endomorphism 0 → 01, 1 → 10.
  • The Fibonacci word is generated over by the endomorphism a → ab, b → a.
  • The tribonacci word is generated over 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 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 ω = limn→∞ σn. 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.