Min-regular languages

Speaker(s)

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

Affiliation

Uniwersytet Warszawski

Date

March 4, 2009, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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

---