Unambiguous Tree Languages Are Topologically Harder Than Deterministic Ones

Prelegent(ci)

Szczepan Hummel

Afiliacja

Uniwersytet Warszawski

Termin

13 czerwca 2012 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

Topological complexity becomes more and more popular set complexity measure in automata theory.
One of its remarkable uses is the separation of the classes of languages.
I will address the question of the topological complexity of unambiguous automata on infinite binary trees, i.e. nondeterministic automata that have at most one accepting run on each tree.

It was shown by Niwiński and Walukiewicz already in the 90's that unambiguous automata recognise not all regular tree languages.
On the other hand, it is not hard to see that they are more expressive than deterministic automata.
However, until now it was not known whether unambiguity introduces any hardness versus determinism from the topological viewpoint.

Deterministic parity tree automata are capable of recognising only sets in Π^1_1 topological class (coanalytic sets).
I will show an example of unambiguous language G that is Σ^1_1 complete (analytic complete), hence is not in Π^1_1.
Then using G, I will show the construction of another unambiguous language that is topologically harder than any set obtained from Σ^1_1 and Π^1_1 sets by countable boolean operations.

If there is enough time, I will relate my examples to the parity index hierarchies.

---