joint work with Mikołaj Bojańczyk

Speaker(s)

Thomas Place

Affiliation

Uniwersytet Warszawski

Date

Jan. 4, 2012, 2:15 p.m.

Room

room 5870

Title in Polish

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

Seminar

Seminar Automata Theory

---

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.

---