The constant of recognizability is computable for primitive morphisms

MaRDI QIDQ2963489zbMATH OpenFDO

Authors Fabien Durand, Julien Leroy

Publication date 14 February 2017

Full work available at URL https://arxiv.org/abs/1610.05577, http://www.emis.de/journals/JIS/VOL20/Leroy/leroy4.html

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

zbMATH Keywords

circularitycombinatorics on wordsrecognizabilitysubstitution

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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.

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

Cited in

(8)

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

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)