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.