You are not logged in |
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”.
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”.
