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 In mathematics, an endomorphism is a morphism from a mathematical object to itself. An endomorphism that is also an isomorphism is an automorphism. For example, an endomorphism of a vector space is a linear map , and an endomorphism of a gr ...

of a

free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...

. Every

automatic sequence In mathematics and theoretical computer science, an automatic sequence (also called a ''k''-automatic sequence or a ''k''-recognizable sequence when one wants to indicate that the base of the numerals used is ''k'') is an infinite sequence of terms ...

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 :

a s f(s) f(f(s)) \cdots f^(s) \cdots \

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 In abstract algebra, the free monoid on a Set (mathematics), set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique seq ...

on ''A''^∗ then the word is ''k''- automatic. The ''n''-th term in such a sequence can be produced by a

finite state automaton A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

reading the digits of ''n'' in base ''k''.

Examples

* The

Thue–Morse sequence In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus ...

is generated over by the 2-uniform endomorphism 0 → 01, 1 → 10.Lothaire (2011) p. 11Lothaire (2005) p.525 * The

Fibonacci word A Fibonacci word is a specific sequence of binary digits (or symbols from any two-letter alphabet). The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition. It is a para ...

is generated over by the endomorphism ''a'' → ''ab'', ''b'' → ''a''.Lothaire (2005) p.524 * The

tribonacci word In mathematics, the Rauzy fractal is a fractal set associated with the Tribonacci substitution : s(1)=12,\ s(2)=13,\ s(3)=1 \,. It was studied in 1981 by Gérard Rauzy, with the idea of generalizing the dynamic properties of the Fibonacci mor ...

is generated over by the endomorphism ''a'' → ''ab'', ''b'' → ''ac'', ''c'' → ''a''. * The

Rudin–Shapiro sequence In mathematics, the Rudin–Shapiro sequence, also known as the Golay–Rudin–Shapiro sequence, is an infinite 2- automatic sequence named after Marcel Golay, Walter Rudin, and Harold S. Shapiro, who independently investigated its properties. ...

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 In mathematics the regular paperfolding sequence, also known as the dragon curve sequence, is an infinite sequence of 0s and 1s. It is obtained from the repeating partial sequence by filling in the question marks by another copy of the whole sequen ...

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

D0L system

A D0L system (deterministic context-free

Lindenmayer system An L-system or Lindenmayer system is a parallel rewriting system and a type of formal grammar. An L-system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into so ...

) 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''→∞ σ^''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

References

* * * *

Definition

Examples

D0L system

See also

References

Further reading