A Hierarchy of Automaticω-Words having a Decidable MSO Theory

DOI10.1051/ita:2008008zbMath1152.03030WikidataQ29395150 ScholiaQ29395150MaRDI QIDQ3526410

Vince Bárány

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

zbMATH Keywords

monadic second-order logic; finite automaton; automatic sequences; morphic words; automatic structures; lexicographic hierarchies; lexicographic word ordering; recognizability by finite automata

Mathematics Subject Classification ID

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

Related Items

The isomorphism problem on classes of automatic structures with transitive relations

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