Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1

Morphisms, Symbolic Sequences, and Their Standard Forms

F. Michel Dekking
Delft University of Technology
Mekelweg 4
2628 CD Delft
The Netherlands


Morphisms are homomorphisms under the concatenation operation of the set of words over a finite alphabet. Changing the elements of the finite alphabet does not change the morphism in an essential way. We propose a method to select a unique representative from all these morphisms. This has applications to the classification of the shift dynamical systems generated by morphisms. In a similar way, we propose the selection of a representing sequence out of the class of symbolic sequences over an alphabet of fixed cardinality. Both methods are useful for the storing of symbolic sequences in databases, such as The On-Line Encyclopedia of Integer Sequences. We illustrate our proposals with the k-symbol Fibonacci sequences.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000078 A000201 A001285 A002828 A003714 A004001 A005206 A007413 A010059 A010060 A035263 A056832 A060143 A080843 A096268 A120613 A120614 A138967 A159917 A216190 A254990 A255014.)

Received August 31 2015; revised version received December 7 2015. Published in Journal of Integer Sequences, December 16 2015.

Return to Journal of Integer Sequences home page