Definable Operations On Weakly Recognizable Sets of Trees

Prelegent(ci)

Alessandro Facchini

Afiliacja

Uniwersytet Warszawski

Termin

15 czerwca 2011 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Filip Murlak and Jacques Duparc

Seminarium

Seminarium „Teoria automatów”

---

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.

---