On the Topological Complexity of Weakly Recognizable Tree Languages
Details
Serval ID
serval:BIB_9B32D184684F
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Institution
Title
On the Topological Complexity of Weakly Recognizable Tree Languages
Title of the conference
Fundamentals of Computation Theory : 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings
Publisher
Springer
ISBN
978-3-540-74239-5
978-3-540-74240-1
978-3-540-74240-1
Publication state
Published
Issued date
2007
Peer-reviewed
Oui
Volume
4639
Series
Lecture Notes on Computer Science
Pages
261-273
Language
english
Abstract
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
Create date
23/01/2008 19:27
Last modification date
20/08/2019 15:02
Usage data
