On Unambiguous Regular Tree Languages of Index (0, 2)

Détails

ID Serval
serval:BIB_5DC9CA1E3285
Type
Actes de conférence (partie): contribution originale à la littérature scientifique, publiée à l'occasion de conférences scientifiques, dans un ouvrage de compte-rendu (proceedings), ou dans l'édition spéciale d'un journal reconnu (conference proceedings).
Collection
Publications
Titre
On Unambiguous Regular Tree Languages of Index (0, 2)
Titre de la conférence
24th EACSL Annual Conference on Computer Science Logic, CSL 2015, September 7-10, 2015, Berlin, Germany
Auteur⸱e⸱s
Duparc J., Fournier K., Hummel S.
Statut éditorial
Publié
Date de publication
2015
Peer-reviewed
Oui
Volume
41
Série
Leibniz International Proceedings in Informatics
Pages
534-548
Langue
anglais
Notes
DBLP:conf/csl/DuparcFH15
Résumé
Unambiguous automata are usually seen as a natural class of automata in-between deterministic and nondeterministic ones. We show that in case of infinite tree languages, the unambiguous ones are topologically far more complicated than the deterministic ones. We do so by providing operations that generate a family (A_{alpha})_{alpha < phi_2(0)} of unambiguous automata such that: 1. It respects the strict Wadge ordering: alpha < beta if and only if A_{alpha} <_W A_{beta}. This can be established without the help of any determinacy principle, simply by providing effective winning strategies in the underlying games. 2. Its length (phi_2(0)) is the first fixpoint of the ordinal function that itself enumerates all fixpoints of the ordinal exponentiation x |-> omega^x: an ordinal tremendously larger than (omega^(omega))^3 +3 which is the height of the Wadge hierarchy of deterministic tree languages as uncovered by Filip Murlak. 3. The priorities of all these parity automata only range from 0 to 2.
Mots-clé
s Tree Automata, Unambiguity, Wadge Hierarchy
Création de la notice
06/04/2016 18:18
Dernière modification de la notice
07/07/2021 13:13
Données d'usage