Regular languages of infinite trees that are boolean combinations of open sets

Prelegent(ci)

Thomas Place

Afiliacja

Uniwersytet Warszawski

Termin

4 stycznia 2012 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Mikołaj Bojańczyk

Seminarium

Seminarium „Teoria automatów”

---

This talk will be about boolean (not necessarily positive)
combinations of open sets. I will present a decidable characterization
of the regular languages of infinite trees that are boolean combination
of open sets. In other words, I will present an algorithm, which inputs a
regular language of infinite trees, and decides if the language is a
boolean combination of open sets. This algorithm uses
algebra and games and will be introduced as a set identities that are satisfied if
and only if a language is a boolean combination of open sets and are
easily decidable.

---