
A coarser version of the Wagner HierarchyJacques 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 omegaregular 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, JeanEric 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 2continuous 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 
