The Wadge Hierarchy of Petri Nets omega-Languages

Details

Serval ID
serval:BIB_08F9DE6D3D34
Type
A part of a book
Collection
Publications
Institution
Title
The Wadge Hierarchy of Petri Nets omega-Languages
Title of the book
Logic, Computation, Hierarchies
Author(s)
Duparc J., Finkel O., Ressayre J-P.
Publisher
De Gruyter
Address of publication
Berlin, Germany
ISBN
978-1-61451-804-4
Publication state
Published
Issued date
2014
Peer-reviewed
Oui
Editor
Brattka V., Diener H., Spreen D.
Volume
4
Series
Ontos Mathematical Logic 4
Pages
109-138
Language
english
Abstract
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.
Keywords
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
Create date
09/09/2014 11:26
Last modification date
08/07/2021 6:36
Usage data