A Tentative Approach for the Wadge-Wagner Hierarchy of Regular Tree Languages of Index [0, 2]

Details

Serval ID
serval:BIB_A65D905A2D05
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Institution
Title
A Tentative Approach for the Wadge-Wagner Hierarchy of Regular Tree Languages of Index [0, 2]
Title of the conference
Descriptional Complexity of Formal Systems: 17th International Workshop, DCFS 2015
Author(s)
Duparc J., Fournier K.
Publisher
Springer, Cham
Address
Waterloo, ON, Canada
ISBN
978-3-319-19224-6
978-3-319-19225-3
Publication state
Published
Issued date
2015
Peer-reviewed
Oui
Volume
9118
Series
Lecture Notes in Computer Science
Pages
81-92
Language
english
Notes
DBLP:conf/dcfs/DuparcF15
June 25-27, 2015. Proceedings
Abstract
We provide a hierarchy of tree languages recognised by nondeterministic parity tree automata with priorities in {0,1,2} , whose length exceeds the first fixed point of the ε operation (that itself enumerates the fixed points of x↦ω^x ). We conjecture that, up to Wadge equivalence, it exhibits all regular tree languages of index [0,2] .
Create date
06/04/2016 17:18
Last modification date
08/07/2021 5:36
Usage data