joint work with Damian Niwiński and Michał Skrzypczak

Speaker(s)

Marcin Przybyłko

Affiliation

Uniwersytet Warszawski

Date

Feb. 22, 2017, 2:15 p.m.

Room

room 5870

Title in Polish

Probability of Regular Sets of Trees

Seminar

Seminar Automata Theory

---

We consider the problem of computing the measure of a regular language of infinite trees with respect to so called coin-flipping measure. While the problem is unsolved in general, some progress
has been made. In this talk I will show that we can compute the measure of language specified by a first order formula using child relations and the letter predicates, discuss the limitations of the algorithm, and compare it to previously known results.

---