On the topological complexity of tree languages

Détails

ID Serval
serval:BIB_ED04090695F1
Type
Partie de livre
Collection
Publications
Institution
Titre
On the topological complexity of tree languages
Titre du livre
Logic and Automata: History and Perspectives
Auteur⸱e⸱s
Arnold A., Duparc J., Murlak F., Niwiński D.
Editeur
Amsterdam University Press
ISBN
9053565760
Statut éditorial
Publié
Date de publication
12/2007
Peer-reviewed
Oui
Editeur⸱rice scientifique
Flum J., Grädel E., Wilke T.
Volume
2
Série
Texts in Logic and Games
Pages
9-28
Langue
anglais
Résumé
The article surveys recent results in the study of topological complexity of recognizable tree languages. Emphasis is put on the relation between topological hierarchies, like the Borel hierarchy or the Wadge hierarchy, and the hierarchies resulting from the structure of automata, as the Rabin-Mostowski index hierarchy. The topological complexity of recognizable tree languages is seen as an evidenceof their structural complexity, which also induces the computational complexity of the verification problems related to automata, as the non-emptiness problem. Indeed, the topological aspect can be seen as a rudiment of the infinite computation complexity theory.
Création de la notice
07/01/2010 18:00
Dernière modification de la notice
08/07/2021 6:36
Données d'usage