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

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 ω = limn→∞ σ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. 1 2 3 4 Lothaire (2005) p.524
  2. Lothaire (2011) p. 10
  3. Honkala (2010) p.505
  4. 1 2 Lothaire (2011) p. 11
  5. 1 2 3 Lothaire (2005) p.525
  6. Lothaire (2005) p.526
  7. Honalka (2010) p.506

Further reading

This article is issued from Wikipedia - version of the Saturday, November 14, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.