Synthesis of Petri Nets from Finite Partial Languages

Issue title: Application of Concurrency to System Design, the Sixth Special Issue

Article type: Research Article

Authors: Bergenthum, Robin | Desel, Jörg | Lorenz, Robert | Mauser, Sebastian

Affiliations: Department of Applied Computer Science, Catholic University of Eichstätt-Ingolstadt, 85072 Eichstätt, Germany. [email protected]

Note: [] Address for correspondence: Department of Applied Computer Science, Catholic University of Eichstätt-Ingolstadt, 85072 Eichstätt, Germany

Abstract: In this paper we present two algorithms that effectively synthesize a finite place/transition Petri net (p/t-net) froma finite set of labeled partial orders (a finite partial language). The synthesized p/t-net either has exactly the non-sequential behavior specified by the partial language, or there is no such p/t-net. The first algorithm is based on the theory of token flow regions for partial languages developed by Lorenz and Juhás. Thus, this paper shows the applicability of this concept. The second algorithm uses the classical theory of regions applied to the set of step sequences generated by the given partial language. We finally develop an algorithm to test whether the net synthesized by either of the two algorithms has exactly the non-sequential behavior specified by the partial language. We implemented all algorithms in our framework VipTool. In this paper, the implementations of the first two algorithms are used to compare the algorithms by means of experimental results.

Journal: Fundamenta Informaticae, vol. 88, no. 4, pp. 437-468, 2008