Synthesis of Petri nets from infinite partial languages
In this paper we present an algorithm to synthesize a finite unlabeled place/transition Petri net (p/t-net) from a possibly infinite partial language, which is given by a term over a finite set of labeled 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 [18] and produces a p/t-net having minimal net behavior including the given partial language. The algorithm uses linear programming techniques that were already successfully applied in [17] for the synthesis of p/t-nets from finite partial languages.
Abstract This paper deals with the complexity of context-free grammars with 1-letter terminal alphabet. We study the complexity of the membership problem and the inequivalence problem. We show that the first problem is NP-complete and the second one is Σ P 2 -complete with respect to log-space reduction. The second result also implies that the inequivalence problem is in P space , solving an open problem stated by Hunt, Rosenkrantz and Szymanski (1976).