The Logical Strength of Büchi's Decidability Theorem

DOI10.4230/LIPIcs.CSL.2016.36zbMath1370.03058OpenAlexW2963236881MaRDI QIDQ5278425

Michał Skrzypczak, Henryk Michalewski, Pierre Pradic, Leszek Aleksander Kołodziejczyk

Publication date: 19 July 2017

Full work available at URL: https://cronfa.swan.ac.uk/Record/cronfa58112/Download/58112__21287__32db592f044540d3a9d874c393b0eda9.pdf

zbMATH Keywords

monadic second-order logicreverse mathematicsnondeterministic automataBüchi's theoremadditive Ramsey theorem

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Second- and higher-order arithmetic and fragments (03F35)

Related Items (2)

Cyclic Arithmetic Is Equivalent to Peano Arithmetic ⋮ A weak variant of Hindman's theorem stronger than Hilbert's theorem

This page was built for publication: The Logical Strength of Büchi's Decidability Theorem