6 citations · 18 across the 8 of their papers we have counts for
4 papers · 1 filter
MSO+nabla is undecidable
Mikołaj Bojańczyk, Edon Kelmendi, Michał Skrzypczak
This paper is about an extension of monadic second-order logic over the full binary tree, which has a quantifier saying ``almost surely a branch π \in {0, 1}^w satisfies a formula…
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 o…
The logical strength of Büchi's decidability theorem
Leszek Kołodziejczyk, Henryk Michalewski, Cécilia Pradic +1
We study the strength of axioms needed to prove various results related to automata on infinite words and Büchi's theorem on the decidability of the MSO theory of . We…
On the Topological Complexity of omega-Languages of Non-Deterministic Petri Nets
Olivier Finkel, Michał Skrzypczak
We show that there are -complete languages of infinite words accepted by non-deterministic Petri nets with Büchi acceptance condition, or equivalently by Büchi blind counter…