Nie jesteś zalogowany |
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”.
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”.
