A Hierarchy of Automaticω-Words having a Decidable MSO Theory
DOI10.1051/ita:2008008zbMath1152.03030WikidataQ29395150 ScholiaQ29395150MaRDI QIDQ3526410
Publication date: 25 September 2008
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/246081
monadic second-order logic; finite automaton; automatic sequences; morphic words; automatic structures; lexicographic hierarchies; lexicographic word ordering; recognizability by finite automata
68R15: Combinatorics on words
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
03B25: Decidability of theories and sets of sentences
68Q42: Grammars and rewriting systems
03D55: Hierarchies of computability and definability
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The monadic second-order logic of graphs. IX: Machines and their behaviours
- Synchronized rational relations of finite and infinite words
- The theory of ends, pushdown automata, and second-order logic
- Iterated GSMs and CO-CFL
- The monadic theory of order
- Monadic second-order logic, graph coverings and unfoldings of transition systems
- Logic and \(p\)-recognizable sets of integers
- Bertrand numeration systems and recognizability
- Monadic second-order logic on tree-like structures
- Finite presentations of infinite structures: Automata and interpretations
- Families of automata characterizing context-sensitive languages
- The monadic theory of morphic infinite words and generalizations
- Automata, logics, and infinite games. A guide to current research
- Decidability questions related to abstract numeration systems
- Automatic graphs and D0L-sequences of finite graphs
- On decidability of monadic logic of order over the naturals extended by monadic predicates
- A topological approach to transductions
- Iterated pushdown automata and sequences of rational numbers
- Automata Presenting Structures: A Survey of the Finite String Case
- Decidable Theories of the Ordering of Natural Numbers with Unary Predicates
- Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
- The Monadic Theory of Tree-like Structures
- Automatic Sequences
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- STACS 2004
- Context-Sensitive Languages, Rational Graphs and Determinism
- A Combinatorial Theorem for Trees
- Mathematical Foundations of Computer Science 2003
- Invariants of Automatic Presentations and Semi-synchronous Transductions
- Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
