Probability of Regular Sets of Trees

Prelegent(ci)

Marcin Przybyłko

Afiliacja

Uniwersytet Warszawski

Termin

22 lutego 2017 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Damian Niwiński and Michał Skrzypczak

Seminarium

Seminarium „Teoria automatów”

---

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.

---