The Wadge Hierarchy of Petri Nets omega-Languages

International audienceWe describe the Wadge hierarchy of the omega-languages recognized by deterministic Petri nets. This is an extension of the celebrated Wagner hierarchy which turned out to be the Wadge hierarchy of the omega-regular languages. Petri nets are more powerful devices than finite automata. They may be defined as partially blind multi-counter automata. We show that the whole hierarchy has height $\omega^{\omega^2}$, and give a description of the restrictions of this hierarchy to partially blind multi-counter automata of some fixed positive number of counters