Descriptive set theoretic methods in automata theory. Decidability and topological complexity
From MaRDI portal
(Redirected from Publication:737116)
automatamonadic second-order logictree automataanalytic setsBorel setsunambiguous automata\(\omega\)-automata\(\omega\)-wordsgame automataweak monadic second-order logic
Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Descriptive set theory (03E15)
Recommendations
- Descriptive set theory and Boolean complexity theory
- Some descriptive-set-theoretical problems in complexity theory
- scientific article; zbMATH DE number 2068876
- \(F\)-sets and finite automata
- Automata theory in nominal sets
- Descriptional and computational complexity of finite automata -- a survey
- Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
- Some problems in automata theory which depend on the models of set theory
- On computational complexity of set automata
- On computational complexity of set automata
Cited in
(10)- The topological complexity of MSO+U and related automata models
- A Characterisation of Pi^0_2 Regular Tree Languages
- Regular languages of thin trees
- scientific article; zbMATH DE number 49206 (Why is no real title available?)
- Some descriptive-set-theoretical problems in complexity theory
- Descriptive set theory, from Cantor to Wadge and beyond
- The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
- On the topological complexity of MSO+U and related automata models
- Wadge-Wagner hierarchies
- Polishness of some topologies related to word or tree automata
This page was built for publication: Descriptive set theoretic methods in automata theory. Decidability and topological complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q737116)
