Inproceedings: An article in a conference proceedings.
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
Lecture Notes on Computer Science
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
Last modification date