How unprovable is Rabin's decidability theorem?

DOI10.1145/2933575.2934543zbMath1394.03016arXiv1508.06780OpenAlexW2964112588MaRDI QIDQ4635942

Henryk Michalewski, Leszek Aleksander Kołodziejczyk

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.06780

zbMATH Keywords

reverse mathematicsmonadic second order logicautomata on infinite treesdeterminacy of infinite gamesRabin's decidability theorem

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35) Determinacy principles (03E60)

Related Items (3)

Unnamed Item ⋮ Unnamed Item ⋮ Monadic Second Order Logic with Measure and Category Quantifiers

This page was built for publication: How unprovable is Rabin's decidability theorem?