Correspondence:
[*]
Address for correspondence: Universität Rostock, Institut für Informatik, Theoretische Informatik, Albert-Einstein-Strasse 22, 18059 Rostock, Germany
Abstract: 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].
