Connecting decidability and complexity for MSO logic

DOI10.1007/978-3-319-62809-7_4MaRDI QIDQ2408793zbMATH OpenOpenAlexFDO

Authors Michał Skrzypczak

Publication date 13 October 2017

Full work available at URL https://doi.org/10.1007/978-3-319-62809-7_4

zbMATH Keywords

decidabilitydescriptive set theorymonadic second-order logicreverse mathematics

Mathematics Subject Classification ID

Higher-order logic (03B16) Decidability of theories and sets of sentences (03B25) Foundations of classical theories (including reverse mathematics) (03B30) Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15)

Recommendations

• On the decidability of MSO+U on infinite trees
• scientific article; zbMATH DE number 6829362
• The logical strength of Büchi's decidability theorem
• The logical strength of Büchi's decidability theorem
• An Extension of Muchnik's Theorem

Cited in

(1)

• On the decidability of MSO+U on infinite trees

This page was built for publication: Connecting decidability and complexity for MSO logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408793)