Computing measures of regular languages via fixpoint expressions

Speaker(s)

Michał Skrzypczak

Affiliation

MIM UW

Date

June 1, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---