Computing measures of regular languages via fixpoint expressions

Prelegent(ci)

Michał Skrzypczak

Afiliacja

MIM UW

Termin

1 czerwca 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

During the talk I will present our ongoing work with Damian Niwiński and Paweł Parys on computing measures of regular languages. Our approach (following earlier results with Marcin Przybyłko) is to reduce the problem to certain fixpoint expression evaluated in a specific ordered set (called Probabilistic Powerdomain). My goal is to present the technique and emphasise its limitations. I will also mention our newest development, which allows us to compute measures of Buchi tree languages (i.e. the existential fragment of MSO). The question about general tree languages remains still open.

---