Nie jesteś zalogowany |
Unambiguity-preserving operations on tree languages that lift topological complexity
- Prelegent(ci)
- Szczepan Hummel
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 28 maja 2014 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
The talk reports my results concerning lower bound for the topological complexity of the class of languages of infinite trees recognized by unambiguous automata.
At the beginning I will show operation sigma that has the following properties:
- if K is the class of languages reducible to language L then all languages in the sigma algebra generated by K are reducible to sigma(L)
- if both, language L and the complement of L, are recognized by unambiguous parity tree automata then so is sigma(L) and the complement of sigma(L) (i.e. sigma preserves bi-unambiguity)
Further we prove that iterating the operation yields topologically harder and harder sets.
Then we show a hierarchy of sets produced by operation sigma and similar limit operations. The height of the hierarchy is omega to the power omega.
The improvement of the lower complexity bound seems to be huge in the context of the results known so far, but the distance to the complexity of all regular languages is still much greater.
At the beginning I will show operation sigma that has the following properties:
- if K is the class of languages reducible to language L then all languages in the sigma algebra generated by K are reducible to sigma(L)
- if both, language L and the complement of L, are recognized by unambiguous parity tree automata then so is sigma(L) and the complement of sigma(L) (i.e. sigma preserves bi-unambiguity)
Further we prove that iterating the operation yields topologically harder and harder sets.
Then we show a hierarchy of sets produced by operation sigma and similar limit operations. The height of the hierarchy is omega to the power omega.
The improvement of the lower complexity bound seems to be huge in the context of the results known so far, but the distance to the complexity of all regular languages is still much greater.
