Synthesis of Petri Nets from Finite Partial Languages

Abstract

In this paper we present an algorithm to synthesize a finite place/transition Petri net (p/t-net) from a finite set of labeled partial orders (a finite partial language). This p/t-net has minimal non-sequential behavior including the specified partial language. Consequently, either this net has exactly the non-sequential behavior specified by the partial language, or there is no such p/t-net. We finally develop an algorithm to test whether the synthesized net has exactly the non-sequential behavior specified by the partial language. The algorithms are based on the theory of regions for partial languages developed by Lorenz and Juhas. Thus, this paper shows the applicability of this concept and, for the first time, provides an effective algorithm for the synthesis of system models from partial languages.