You are not logged in | log in

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Automata Theory


Computing measures of regular languages via fixpoint expressions

Prelegent: Michał Skrzypczak

2022-06-01 14:15

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.