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

Autor:	Kevin Fournier, Jacques Duparc
Rok vydání:	2015
Předmět:	Discrete mathematics Nondeterministic algorithm Combinatorics Regular tree Conjecture Pointclass Fixed point Equivalence (formal languages) Omega Computer Science::Formal Languages and Automata Theory Wadge hierarchy Mathematics
Zdroj:	Descriptional Complexity of Formal Systems ISBN: 9783319192246 DCFS
Popis:	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 \(\varepsilon \) operation (that itself enumerates the fixed points of \(x\mapsto \omega ^x\)). We conjecture that, up to Wadge equivalence, it exhibits all regular tree languages of index \([0,2]\).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::55b143443c986d06fe4e621c48a3cfb1 https://doi.org/10.1007/978-3-319-19225-3_7 Zobrazit plný text záznamu