The Wadge Hierarchy of Petri Nets omega-Languages

Détails

ID Serval
serval:BIB_08F9DE6D3D34
Type
Partie de livre
Collection
Publications
Institution
Titre
The Wadge Hierarchy of Petri Nets omega-Languages
Titre du livre
Logic, Computation, Hierarchies
Auteur(s)
Duparc J., Finkel O., Ressayre J-P.
Editeur
De Gruyter
Lieu d'édition
Berlin, Germany
ISBN
978-1-61451-804-4
Statut éditorial
Publié
Date de publication
2014
Editeur scientifique
Brattka V., Diener H., Spreen D.
Volume
4
Série
Ontos Mathematical Logic 4
Pages
109-138
Langue
anglais
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 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.
Mots-clé
Automata theory, languages of infinite words, Petri nets, partially blind multicounter automata, Cantor topology, topological complexity, Borel and Wadge hierarchies, Wadge degrees
Web of science
Création de la notice
09/09/2014 10:26
Dernière modification de la notice
20/08/2019 12:31
Données d'usage