The wadge hierarchy of Petri Nets ω-languages
Jacques Duparc, Olivier Finkel, Jean-Pierre Ressayre · 2014
We describe the Wadge hierarchy of the ω-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 ω-regular languages. Petri nets are an improvement of automata. They may be defined as partially blind multi-counter automata. We show that the whole hierarchy has height ω ω2, and give a description of the restrictions of this hierarchy to every fixed number of partially blind counters.