A Hierarchy of Automaticω-Words having a Decidable MSO Theory
DOI10.1051/ITA:2008008zbMATH Open1152.03030DBLPjournals/ita/Barany08OpenAlexW2087899139WikidataQ29395150 ScholiaQ29395150MaRDI QIDQ3526410FDOQ3526410
Authors: 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
Recommendations
- Deciding monadic second order logic over \(\omega \)-words by specialized finite automata
- Infinite trees and automaton-definable relations over \(\omega\)-words
- Brzozowski hierarchy of \(\omega\)-languages
- Infinite and bi-infinite words with decidable monadic theories
- The monadic theory of morphic infinite words and generalizations
automatic structuresmonadic second-order logicautomatic sequencesfinite automatonmorphic wordslexicographic hierarchieslexicographic word orderingrecognizability by finite automata
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42) Combinatorics on words (68R15) Decidability of theories and sets of sentences (03B25) Hierarchies of computability and definability (03D55)
Cites Work
- The monadic theory of morphic infinite words and generalizations
- Title not available (Why is that?)
- Automata Presenting Structures: A Survey of the Finite String Case
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Automatic Sequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- STACS 2004
- Mathematical Foundations of Computer Science 2003
- Logic and \(p\)-recognizable sets of integers
- Monadic second-order logic on tree-like structures
- Automata, logics, and infinite games. A guide to current research
- Title not available (Why is that?)
- Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
- Title not available (Why is that?)
- The theory of ends, pushdown automata, and second-order logic
- Synchronized rational relations of finite and infinite words
- The monadic theory of order
- Iterated pushdown automata and sequences of rational numbers
- A topological approach to transductions
- Title not available (Why is that?)
- Automatic graphs and D0L-sequences of finite graphs
- Bertrand numeration systems and recognizability
- A Combinatorial Theorem for Trees
- Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
- On decidability of monadic logic of order over the naturals extended by monadic predicates
- Title not available (Why is that?)
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- The monadic second-order logic of graphs. IX: Machines and their behaviours
- Finite presentations of infinite structures: Automata and interpretations
- Decidable Theories of the Ordering of Natural Numbers with Unary Predicates
- Title not available (Why is that?)
- Monadic second-order logic, graph coverings and unfoldings of transition systems
- Context-Sensitive Languages, Rational Graphs and Determinism
- Iterated GSMs and CO-CFL
- The Monadic Theory of Tree-like Structures
- Title not available (Why is that?)
- Invariants of Automatic Presentations and Semi-synchronous Transductions
- Families of automata characterizing context-sensitive languages
- Title not available (Why is that?)
- Decidability questions related to abstract numeration systems
Cited In (4)
This page was built for publication: A Hierarchy of Automaticω-Words having a Decidable MSO Theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3526410)
