A Coarsification of the Wagner Hierarchy

Détails

ID Serval
serval:BIB_0C4E3C9581A1
Type
Non publié: un document ayant un auteur et un titre, mais non publié.
Collection
Publications
Institution
Titre
A Coarsification of the Wagner Hierarchy
Auteur⸱e⸱s
Duparc J.
Langue
anglais
Notes
submitted to Theoretical Computer Science
Résumé
In 1979, Klaus W. Wagner introduced a hierarchy on ω-regular sets that has length ωω . It is the one induced by the ordering on Deterministic Automata: A < B iff the set accepted by A is the inverse image of the set accepted by B by a continuous function. Lately, Jean-Eric Pin conjectured that there might be a coarser hierarchy with length ω and that it could be given by the same ordering on DA except that continuous is replaced by a slightly weaker notion 2-continuous. We provide a positive answer to this conjecture and give a description of this new hierarchy.
Création de la notice
23/01/2008 20:48
Dernière modification de la notice
08/07/2021 6:36
Données d'usage