Comparison of Different Algorithms to Synthesize a Petri Net from a Partial Language

In this paper we present two new algorithms that effectively synthesize a finite place/transition Petri net (p/t-net) from a finite set of labeled partial orders (a finite partial language). Either the synthesized p/t-net has exactly the non-sequential behavior specified by the partial language, or there is no such p/t-net. The first algorithm is an improved version of a synthesis algorithm presented in [14], which uses the classical theory of regions applied to the set of step sequences generated by the given partial language. Instead of computing all step sequences, the new algorithm directly works on appropriate prefixes specified in the partial language. The second algorithm is based on the theory of token flow regions for partial languages developed in [16,15,14]. While in [15,14] a so called basis representation is applied, the new algorithm combines the concepts of separation representation and token flows. We implemented both synthesis algorithms in our framework VipTool. A comparison of the two new algorithms with the two predecessor algorithms presented in [14,15]shows that both perform better than their respective predecessor. Therefore, a detailed comparison of these two synthesis algorithms is presented.