scientific article; zbMATH DE number 7058775

MaRDI QIDQ5377469

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

Publication date: 24 May 2019

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

monadic second-order logicreverse mathematicsnondeterministic automataBüchi's theoremadditive Ramsey's 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)

Unnamed Item ⋮ On the Weihrauch degree of the additive Ramsey theorem over the rationals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Observations on determinization of Büchi automata
• The monadic theory of order
• On decidability of monadic logic of order over the naturals extended by monadic predicates
• RT₂² does not imply WKL₀
• Complementation, Disambiguation, and Determinization of Büchi Automata Unified
• A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata
• AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
• How unprovable is Rabin's decidability theorem?
• On the Ramseyan Factorization Theorem
• Testing and generating infinite sequences by a finite automaton
• Ramsey's theorem and recursion theory

This page was built for publication: