Search

• < Previous
• 1
• Next >

---

The logical strength of B\"uchi's decidability theorem

Leszek Kołodziejczyk ; Henryk Michalewski ; Pierre Pradic ; Michał Skrzypczak.

We study the strength of axioms needed to prove various results related to automata on infinite words and B\"uchi's theorem on the decidability of the MSO theory of $(N, {\le})$. We prove that the following are equivalent over the weak second-order arithmetic theory $RCA_0$: (1) the induction&nbsp;[&hellip;]

---

Monadic Second Order Logic with Measure and Category Quantifiers

Matteo Mio ; Michał Skrzypczak ; Henryk Michalewski.

We investigate the extension of Monadic Second Order logic, interpreted over infinite words and trees, with generalized "for almost all" quantifiers interpreted using the notions of Baire category and Lebesgue measure.

---