The monadic theory of morphic infinite words and generalizations

DOI10.1006/inco.2001.3139zbMath1012.03015OpenAlexW2008735821MaRDI QIDQ1854542

Wolfgang Thomas, Olivier Carton

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.3139

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (17)

On Boolean closed full trios and rational Kripke frames ⋮ Operations preserving regular languages ⋮ On decidability of monadic logic of order over the naturals extended by monadic predicates ⋮ Decidable problems in substitution shifts ⋮ Sturmian and Infinitely Desubstitutable Words Accepted by an $$\omega $$-Automaton ⋮ A Hierarchy of Automaticω-Words having a Decidable MSO Theory ⋮ From Combinatorial Games to Shape-Symmetric Morphisms ⋮ The Church problem for expansions of \((\mathbb{N},<)\) by unary predicates ⋮ Multidimensional generalized automatic sequences and shape-symmetric morphic words ⋮ On Monadic Theories of Monadic Predicates ⋮ Decidable Expansions of Labelled Linear Orderings ⋮ Unnamed Item ⋮ Decidable Extensions of Church’s Problem ⋮ ON UNIFORMLY RECURRENT MORPHIC SEQUENCES ⋮ Regular sets over extended tree structures ⋮ 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05 ⋮ On a question of Hof, Knill and Simon on palindromic substitutive systems

Cites Work

• The theory of successor with an extra predicate
• Linear cellular automata, finite automata and Pascal's triangle
• Decidability and undecidability of theories with a predicate for the primes
• On the bounded monadic theory of well-ordered structures
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Definability in the monadic second-order theory of successor
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The monadic theory of morphic infinite words and generalizations