joint work with Filip Murlak and Jacques Duparc

Speaker(s)

Alessandro Facchini

Affiliation

Uniwersytet Warszawski

Date

June 15, 2011, 2:15 p.m.

Room

room 5870

Title in Polish

Definable Operations On Weakly Recognizable Sets of Trees

Seminar

Seminar Automata Theory

---

We introduce a class of alternating tree automata, called game automata, which is the largest class  for which the substitution operation preserves Wadge equivalence. Moreover it contains all deterministic automata.
We then show that for the subclass of weak game automata, the following facts hold:
- the Wadge hierarchy is decidable,
- the weak index hierarchy and the Borel hierarchy coincide.
As a corollary we obtain that the weak index problem for this class is also decidable.

---