2023/03/20 by Pierre Béaur, Béaur, Pierre, Benjamin Hellouin de Ménibus +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Chemical Synthesis and Analysis #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2303.11133
openalex publication_date 2023/03/20 · openalex created_date 2023/03/23 · openalex updated_date 2026/07/28
Given an ω-automaton and a set of substitutions, we look at which accepted words can also be defined through these substitutions, and in particular if there is at least one. We introduce a method using desubstitution of ω-automata to describe the structure of preimages of accepted words under arbitrary sequences of homomorphisms: this takes the form of a meta-ω-automaton. We decide the existence of an accepted purely substitutive word, as well as the existence of an accepted fixed point. In the case of multiple substitutions (non-erasing homomorphisms), we decide the existence of an accepted infinitely desubstitutable word, with possibly some constraints on the sequence of substitutions e.g. Sturmian words or Arnoux-Rauzy words). As an application, we decide when a set of finite words codes e.g. a Sturmian word. As another application, we also show that if an ω-automaton accepts a Sturmian word, it accepts the image of the full shift under some Sturmian morphism.