Min-regular languages

Prelegent(ci)

Szymon Toruńczyk (joint work with Mikołaj Bojańczyk)

Afiliacja

Uniwersytet Warszawski

Termin

4 marca 2009 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

A new class of languages of infinite words is introduced, called the min-regular languages, extending the class of omega-regular languages. Min-regular languages are somehow dual to max-regular languages introduced before. The class has two equivalent descriptions: in terms of automata (a type of deterministic counter automaton), and in terms of logic (weak monadic second-order logic with a bounding quantifier).

---