On the topological complexity of tree languages

Details

Serval ID
serval:BIB_ED04090695F1
Type
A part of a book
Collection
Publications
Institution
Title
On the topological complexity of tree languages
Title of the book
Logic and Automata: History and Perspectives
Author(s)
Arnold A., Duparc J., Murlak F., Niwiński D.
Publisher
Amsterdam University Press
ISBN
9053565760
Publication state
Published
Issued date
12/2007
Peer-reviewed
Oui
Editor
Flum J., Grädel E., Wilke T.
Volume
2
Series
Texts in Logic and Games
Pages
9-28
Language
english
Abstract
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.
Create date
07/01/2010 17:00
Last modification date
08/07/2021 5:36
Usage data