Personal tools
You are here: Home Events Abstract Archives 2005 A coarser version of the Wagner Hierarchy

A coarser version of the Wagner Hierarchy

Jacques Duparc Institut d'Informatique et Organisation Universite de Lausanne 4pm 15 February 2005 Room 2511, JCMB, King's Buildings

In 1979, Klaus W. Wagner introduced a hierarchy on omega-regular sets that has length omega to the omega.

It is induced by the ordering on Deterministic Automata: A is Wadge less than or equal to B iff the set of infinite words accepted by A is the inverse image of the set of infinite words accepted by B, by a continuous function.

Lately, Jean-Eric Pin, and Dominique Perrin inquired whether there was a coarser hierarchy with length omega, that would identify any Deterministic Automaton with one bearing a strongly connected graph. They also conjectured that it could be obtained by using a version of the Wagner ordering on DA where continuous functions are replaced by 2-continuous functions. A slightly weaker notion, based on the fact that countable union of closed sets (as opposed to open sets) are preserved by inverse image.

We give a positive answer to this conjecture and describe this new hierarchy. The main tools are different versions of reduction games intimately related to the Wadge game.

Document Actions