Descriptive set theoretic methods in automata theory. Decidability and topological complexity
DOI10.1007/978-3-662-52947-8zbMATH Open1375.03003OpenAlexW4252107771MaRDI QIDQ737116FDOQ737116
Authors: Michał Skrzypczak 
Publication date: 5 August 2016
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-52947-8
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
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)
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
- Title not available (Why is that?)
- 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)
