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

DOI10.1007/978-3-031-33180-0_8arXiv2303.11133OpenAlexW4381304098MaRDI QIDQ6134866FDOQ6134866

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)

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.

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)

Cites Work

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

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)