The Constant of Recognizability is Computable for Primitive Morphisms
Fabien Durand
Laboratoire Amiénois de Mathématiques Fondamentales
et Appliquées
CNRS-UMR 7352
Université de Picardie Jules Verne
33 rue Saint Leu
80000 Amiens
France
Julien Leroy
Institut de mathématique
Université de Liège
Allée de la découverte 12 (B37)
4000 Liège
Belgium
Abstract:
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
