Synthesis of Petri Nets from Term Based Representations of Infinite Partial Languages

Issue title: Application of Concurrency to System Design

Article type: Research Article

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

Affiliations: Department of Applied Computer Science, Catholic University of Eichstätt-Ingolstadt, Germany. E-mail: firstname.lastname@ku-eichstaett.de | Department of Computer Science, University of Augsburg, Germany. E-mail: robert.lorenz@informatik.uni-augsburg.de

Abstract: In this paper we present an algorithm to synthesize a finite unlabelled place/transition Petri net (p/t-net) from a possibly infinite partial language, which is given by a term over a finite set of labelled partial orders using operators for union, iteration, parallel composition and sequential composition. The synthesis algorithm is based on the theory of regions for partial languages presented in [17] and produces a p/t-net having minimal net behaviour including the given partial language. The algorithm uses linear programming techniques that were already successfully applied in [22] for the synthesis of p/t-nets from finite partial languages. Also, an equality test algorithm to check whether the behaviour of the synthesized p/t-net equals the given partial language is shown. Moreover, we present an implementation of the developed synthesis algorithm together with an example case study. Finally, a possible generalization of the presented term based representation of infinite partial languages is discussed.

DOI: 10.3233/FI-2009-147

Journal: Fundamenta Informaticae, vol. 95, no. 1, pp. 187-217, 2009