Mots Sturmiens et infiniment désubstituables acceptés par un ω-automate
| Autor: | Béaur, Pierre, de Menibus, Benjamin Hellouin |
|---|---|
| Přispěvatelé: | Graphes, Algorithmes et Combinatoire (GALaC), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Algorithmes, Apprentissage et Calcul (AAC), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
ω-automata Discrete Mathematics (cs.DM) [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] Formal Languages and Automata Theory (cs.FL) [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics decidability Combinatorics (math.CO) Sturmian words Substitutions |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|