Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.5

The Constant of Recognizability is Computable for Primitive Morphisms

Fabien Durand
Laboratoire Amiénois de Mathématiques Fondamentales et Appliquées
Université de Picardie Jules Verne
33 rue Saint Leu
80000 Amiens

Julien Leroy
Institut de mathématique
Université de Liège
Allée de la découverte 12 (B37)
4000 Liège


Mossé proved that primitive morphisms are recognizable. In this paper we give a computable upper bound for the constant of recognizability of such a morphism. This bound can be expressed using only the cardinality of the alphabet and the length of the longest image of a letter under the morphism.

Full version:  pdf,    dvi,    ps,    latex    

Received October 14 2016; revised versions received November 9 2016; January 26 2016; February 6 2017. Published in Journal of Integer Sequences, February 10 2017.

Return to Journal of Integer Sequences home page