Nie jesteś zalogowany |
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
- 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.
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.
