The Wadge Hierarchy of Petri Nets \emph\(\omega\)-Languages

Details

Serval ID
serval:BIB_C002A9B1A2FF
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Institution
Title
The Wadge Hierarchy of Petri Nets \emph\(\omega\)-Languages
Title of the conference
Logical Foundations of Computer Science, International Symposium, LFCS 2013, January 6-8, 2013. Proceedings
Author(s)
Duparc J., Finkel O., Ressayre J.-P.
Address
San Diego, CA, USA
ISSN
0302-9743
Publication state
Published
Issued date
2013
Peer-reviewed
Oui
Volume
7734
Series
Lecture Notes in Computer Science
Pages
179-193
Language
english
Notes
DBLP:conf/lfcs/DuparcFR13
Abstract
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.
Keywords
Wadge Hierarchy,Regular Language, Automata, Petrinet, Deterministic
Create date
09/09/2014 11:13
Last modification date
08/07/2021 6:36
Usage data