Max-regular languages

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

8 października 2008 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

A new class of languages of infinite words is introduced, called the max-regular languages, extending the class of omega-regular languages. 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). Effective translations between the logic and automata are given.

---