On B. Mossé's unilateral recognizability theorem

2017/12/27 by Akiyama, Shigeki, Tan, Bo, Yuasa, Hisatoshi
#37B10 #68R15 #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1801.03536

Abstract

We complete statement and proof for B. Mossé's unilateral recognizability theorem. We also provide an algorithm for deciding the unilateral non-recognizability of a given primitive substitution.

Related

• The constant of recognizability is computable for primitive morphisms
• A note on one-sided recognizable morphisms
• Decidable problems in substitution shifts
• Recognizability of morphisms
• Undecidability in Finite Transducers, Defense Systems and Finite Substitutions