Complements of unambiguous languages.

Speaker(s)

Marcin Bilkowski

Affiliation

Uniwersytet Warszawski

Date

March 16, 2011, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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

---