The constant of recognizability is computable for primitive morphisms

zbMATH Open1359.68239arXiv1610.05577MaRDI QIDQ2963489FDOQ2963489

Authors: Fabien Durand, Julien Leroy 

Publication date: 14 February 2017

Abstract: Moss'e 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.

Full work available at URL: https://arxiv.org/abs/1610.05577

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Primitive morphisms
• Complexity of testing morphic primitivity
• Recognizability for sequences of morphisms
• Reconnaissabilité des substitutions et complexité des suites automatiques
• scientific article; zbMATH DE number 1004349

zbMATH Keywords

combinatorics on wordssubstitutionrecognizabilitycircularity

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cited In (6)

• On Substitutions Preserving Their Return Sets
• Homomorphisms between multidimensional constant-shape substitutions
• Recognizability for sequences of morphisms
• Automatic abelian complexities of Parikh-collinear fixed points
• Automaticity and Parikh-Collinear Morphisms
• Graph towers, laminations and their invariant measures

This page was built for publication: The constant of recognizability is computable for primitive morphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963489)