Descriptive set theoretic methods in automata theory. Decidability and topological complexity

DOI10.1007/978-3-662-52947-8zbMath1375.03003OpenAlexW4252107771MaRDI QIDQ737116

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

zbMATH Keywords

automatamonadic second-order logicanalytic setsBorel setstree automata\(\omega\)-automata\(\omega\)-wordsunambiguous automatagame automataweak monadic second-order logic

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive set theory (03E15) 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)

Related Items (4)

Descriptive set theory, from Cantor to Wadge and beyond ⋮ Polishness of some topologies related to word or tree automata ⋮ Wadge-Wagner hierarchies ⋮ A Characterisation of Pi^0_2 Regular Tree Languages

This page was built for publication: Descriptive set theoretic methods in automata theory. Decidability and topological complexity