The synthesis problem for elementary net systems is NP-complete

Given a labelled graph representing the sequential behaviour of some system, the synthesis problem consists in deciding whether it is the behaviour of a Petri net. This problem was solved by Ehrenfeucht and Rozenberg for the class of elementary net systems, relying on regions in graphs introduced as sets of nodes liable to represent extensions of places of a net. The solution was extended later on to pure place/transition nets using a variant notion of generalized regions. The naive method of synthesis which relies on this principle leads to exponential algorithms for an arbitrary class of nets. In an earlier study, we gave an algorithm that solves the synthesis problem in polynomial time for the class of pure place/transition nets. We show here that in contrast the synthesis problem is indeed NP-complete for the class of elementary nets.