Definable Operations On Weakly Recognizable Sets of Trees
Détails
ID Serval
serval:BIB_EBB4FD4B6C9F
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
Institution
Titre
Definable Operations On Weakly Recognizable Sets of Trees
Titre de la conférence
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, December 12-14, 2011, Mumbai, India
Statut éditorial
Publié
Date de publication
2011
Peer-reviewed
Oui
Volume
13
Série
Leibniz International Proceedings in Informatics
Pages
363-374
Langue
anglais
Notes
DBLP:conf/fsttcs/DuparcFM11
Résumé
Alternating automata on infinite trees induce operations on languages which do not preserve natural equivalence relations, like having the same Mostowski--Rabin index, the same Borel rank, or being continuously reducible to each other (Wadge equivalence). In order to prevent this, alternation needs to be restricted to the choice of direction in the tree. For weak alternating automata with restricted alternation a small set of computable operations generates all definable operations, which implies that the Wadge degree of a given automaton is computable. The weak index and the Borel rank coincide, and are computable. An equivalent automaton of minimal index can be computed in polynomial time (if the productive states of the automaton are given).
Mots-clé
alternating automata, Wadge hierarchy, index hierarchy
Web of science
Site de l'éditeur
Création de la notice
09/09/2014 10:09
Dernière modification de la notice
08/07/2021 5:36