2016/10/18 by Fabien Durand, Durand, Fabien, Julien Leroy +1
Computer Science · #68R15 #Cellular Automata and Applications #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1610.05577
openalex publication_date 2016/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 only using the cardinality of the alphabet and the length of the longest image under the morphism of a letter.