2.1k citations · 3.9k across the 42 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.FL2015★ 2 cited
On the Problem of Computing the Probability of Regular Sets of Trees
Henryk Michalewski, Matteo Mio
We consider the problem of computing the probability of regular languages of infinite trees with respect to the natural coin-flipping measure. We propose an algorithm which compute…
math.LO2015
How unprovable is Rabin's decidability theorem?
Leszek Aleksander Kołodziejczyk, Henryk Michalewski
We study the strength of set-theoretic axioms needed to prove Rabin's theorem on the decidability of the MSO theory of the infinite binary tree. We first show that the complementat…