The Wadge Hierarchy of Petri Nets omega-Languages - Logique
Communication Dans Un Congrès Année : 2013

The Wadge Hierarchy of Petri Nets omega-Languages

Résumé

We 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 an improvement of 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 some fixed number of partially blind counters.
Fichier principal
Vignette du fichier
LFCS2013.pdf (235.38 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00799936 , version 1 (12-03-2013)

Identifiants

Citer

Jacques Duparc, Olivier Finkel, Jean-Pierre Ressayre. The Wadge Hierarchy of Petri Nets omega-Languages. International Symposium on Logical Foundations of Computer Science, LFCS 2013, Jan 2013, San Diego, United States. pp.179-193, ⟨10.1007/978-3-642-35722-0_13⟩. ⟨hal-00799936⟩
303 Consultations
141 Téléchargements

Altmetric

Partager

More