Report LRI--501. Univ. de Paris-Sud, Centre d'Orsay, Laboratoire de Recherche en Informatique, June 1989.
Abstract: The author presents the minimal coverability graph for Petri nets and for Vector Addition Systems. This graph is based on an optimization of the Karp and Miller's graph. It allows to decide the Finite Reachability Tree Problem, the Finite Reachability Set Problem, the Boundedness Problem, the Coverability Problem, the Quasi-Lifeness Problem and the Regularity Problem. The algorithm given for computing the minimal coverability graph uses as less as possible the memory.
Keywords: minimal coverability graph; vector addition system; Karp (and) Miller's graph; finite reachability tree; finite reachability set; boundedness; quasi lifeness; regularity.
Back to the Petri Nets Bibliography