On the Topological Complexity of Weakly Recognizable Tree Languages
Détails
ID Serval
serval:BIB_9B32D184684F
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
On the Topological Complexity of Weakly Recognizable Tree Languages
Titre de la conférence
Fundamentals of Computation Theory : 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings
Editeur
Springer
ISBN
978-3-540-74239-5
978-3-540-74240-1
978-3-540-74240-1
Statut éditorial
Publié
Date de publication
2007
Peer-reviewed
Oui
Volume
4639
Série
Lecture Notes on Computer Science
Pages
261-273
Langue
anglais
Résumé
We show that the family of tree languages recognized by weak alternating automata is closed by three set theoretic operations that correspond to sum, multiplication by ordinals < omega(omega), and pseudo-exponentiation with the base omega(1) of the Wadge degrees. In consequence, the Wadge hierarchy of weakly recognizable tree languages has the height of at least epsilon(0), that is the least fixed point of the exponentiation with the base omega.
Web of science
Création de la notice
23/01/2008 20:27
Dernière modification de la notice
20/08/2019 16:02
Données d'usage
