Sturmian and Infinitely Desubstitutable Words Accepted by an \omega -Automaton

DOI10.1007/978-3-031-33180-0_8MaRDI QIDQ6134866zbMATH OpenOpenAlexFDO

Authors Pierre Béaur, Benjamin Hellouin de Menibus

Publication date 25 July 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

decidabilitySturmian wordssubstitutions\( \omega \)-automata

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: Given an $omega$-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 $omega$-automata to describe the structure of preimages of accepted words under arbitrary sequences of homomorphisms: this takes the form of a meta-$omega$-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 $omega$-automaton accepts a Sturmian word, it accepts the image of the full shift under some Sturmian morphism.

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• -adic characterization of minimal ternary dendric shifts
• A note on Sturmian words
• An Introduction to Symbolic Dynamics and Coding
• Asymptotic enumeration of minimal automata
• Decidability and universality of quasiminimal subshifts
• Initial powers of Sturmian sequences
• On sets of indefinitely desubstitutable words
• Rank and symbolic complexity
• Représentation géométrique de suites de complexité $2n+1$
• The monadic theory of morphic infinite words and generalizations

This page was built for publication: Sturmian and Infinitely Desubstitutable Words Accepted by an $$\omega $$-Automaton

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