A Coarsification of the Wagner Hierarchy

Details

Serval ID
serval:BIB_0C4E3C9581A1
Type
Unpublished: a document having an author and title, but not formally published.
Collection
Publications
Title
A Coarsification of the Wagner Hierarchy
Author(s)
Duparc J.
Language
english
Notes
submitted to Theoretical Computer Science
Abstract
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.
Create date
23/01/2008 19:48
Last modification date
20/08/2019 12:33
Usage data