Search

• < Previous
• 1
• Next >

---

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.

---

Regular tree languages in low levels of the Wadge Hierarchy

Mikołaj Bojańczyk ; Filippo Cavallari ; Thomas Place ; Michał Skrzypczak.

In this article we provide effective characterisations of regular languages of infinite trees that belong to the low levels of the Wadge hierarchy. More precisely we prove decidability for each of the finite levels of the hierarchy; for the class of the Boolean combinations of open sets&nbsp;[&hellip;]

---

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;]

---