Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Tarjans union/find algorithm

Sortuj według:

Ogranicz wyniki do:

Synthesis for Various Petri Net Classes with Union/Find

Wolf Karsten

Fundamenta Informaticae

2019

Vol. 169, nr 1-2

57--84

We propose a new algorithmic approach for the synthesis of a Petri net from a transition system. It is first presented for a class of place/transition Petri nets we call Δ1-Petri nets. A Δ1-Petri net has an incidence matrix where entries have values 0, 1, and -1 only. The algorithm employs Tarjans 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. We further present ideas for adapting the method to various classes of Petri nets, including pure (loop-free), safe and k-bounded, ordinary nets as subclasses of Δ-1-Petri nets as well as an extension to Δk-Petri nets. This article is an extended version of [1].