The Probabilistic Rabin Tree Theorem

The Rabin tree theorem yields an algorithm to solve the satisfiability problem for monadic second-order logic over infinite trees. Here we solve the probabilistic variant of this problem. Namely, we show how to compute the probability that a randomly chosen tree satisfies a given formula. We additionally show that this probability is an algebraic number. This closes a line of research where similar results were shown for formalisms weaker than the full monadic second-order logic. Joint work with Damian Niwiński and Michał Skrzypczak, submitted (under review). Contributed talk given by Paweł Parys

Authors

• Paweł Parys

Keywords

No keywords are indexed for this paper.