Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Petri Net Synthesis with Union/Find
verfasst von : Karsten Wolf
Erschienen in: Application and Theory of Petri Nets and Concurrency
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We propose a new algorithm for the synthesis of a Petri net from a transition system. It is presented for a class of place/transition Petri nets we call \(\varDelta \)1-Petri nets. A \(\varDelta \)1-Petri net has an incidence matrix where entries have values 0, 1, and −1 only. This class includes safe Petri nets as well as ordinary place/transition nets. The proposed algorithm can be adapted to these net classes. The algorithm employs Tarjan’s union/find algorithm for managing sets of vertices. It requires just O(|V||T|) space where V is the set of vertices and T is the set of transition labels. Consequently, problem instances even beyond 1,000,000 vertices have a manageable memory footprint. Our results are experimentally validated using a prototype implementation.