Nie jesteś zalogowany | Zaloguj się

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
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.