Complements of unambiguous languages.

Prelegent(ci)

Marcin Bilkowski

Afiliacja

Uniwersytet Warszawski

Termin

16 marca 2011 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

An automaton is unambiguous if it has at most one accepting run for every input.
A language is unambiguous if there exists an unambiguous automaton recognizing
that language. It is known that not all regular languages of infinite trees are unambiguous.

Our goal is to show that it is decidable if a complement of the unambiguous
regular language is also unambiguous. For this purpose we split all regular
languages into two groups - “thin languages” and “thick languages”.

---