HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

The Synthesis Problem for Elementary Net Systems is NP-Complete

Eric Badouel 1 Luca Bernardinello 1 Philippe Darondeau 1
1 MICAS - Modèles et implémentation des calculs syntaxiques
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : The so-called synthesis problem consists in deciding for a class of nets whether a given graph is isomorphic to the case graph of some net and then constructing the net. This problem has been solved for various classes of nets, ranging from elementary nets to Petri nets. The general principle is to compute regions in the graph, i.e. subsets of nodes liable to represent extensions of places of an associated net. 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 algorithms that solve the synthesis problem in polynomial time for the class of bounded Petri nets. We show here that in contrast the synthesis problem is indeed NP-complete for the class of elementary nets. This result is independent from the results of Kunihiko Hiraishi, showing that both problems of separation and inhibition by regions at a given node of the graph are NP-complete.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:33:52 PM
Last modification on : Friday, February 4, 2022 - 3:25:31 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:53:24 PM


  • HAL Id : inria-00074122, version 1


Eric Badouel, Luca Bernardinello, Philippe Darondeau. The Synthesis Problem for Elementary Net Systems is NP-Complete. [Research Report] RR-2558, INRIA. 1995. ⟨inria-00074122⟩



Record views


Files downloads