Rüdiger Valk and Matthias Jantzen.

The residue of vector sets with applications to decidability problems
in Petri nets.

In Grzegorz Rozenberg, Hartmann Genrich, and Gérard Roucairol,
editors, *Advances in Petri Nets 1984 European Workshop on
Applications and Theory in Petri Nets, covers the last two years which
include the workshop 1983 in Toulouse and the workshop 1984 in Aarhus,
selected papers*, volume 188 of *Lecture Notes in Computer Science*,
pages 234-258, Berlin, Heidelberg, New York, 1985. Springer-Verlag.

Abstract:No abstracts yet.

@inproceedings{Jantzen+85b, Abstract = {A set $K$ of integer vectors is called right-closed, if for any element $m\in K$ all vectors $m\geq m$ are also contained in $K$. In such a case $K$ is a semilinear set of vectors having a minimal generating set $\mathrm{res}(K)$, called the residue of $K$. A general method is given for computing the residue set of a right-closed set, provided it satisfies a certain decidability criterion. Various right-closed sets which are important for analyzing, constructing, or controlling Petri nets are studied. One such set is the set $\mathrm{CONTINUAL}(T)$ of all such markings which have an infinite continuation using each transition infinitely many times. It is shown that the residue set of $\mathrm{CONTINUAL}(T)$ can be constructed effectively, solving an open problem of Schroff. The proof also solves problem 24 (iii) in the EATCS-Bulletin. The new methods developed in this paper can also be used to show that it is decidable, whether a signal net is prompt [Patil] and whether certain -languages of a Petri net are empty or not. It is shown, how the behaviour of a given Petri net can be controlled in a simple way in order to realize its maximal central subbehaviour, thereby solving a problem of Nivat and Arnold, or its maximal live subbehaviour as well. This latter approach is used to give a new solution for the bankers problem described by Dijkstra. Since the restriction imposed on a Petri net by a fact [Genrich, Lautenbach] can be formulated as a right closed set, our method also gives a new general approach for implementations of facts.}, Address = Springer.addr, Author = {Valk, R{\"u}diger and Jantzen, Matthias}, Booktitle = {Advances in {Petri} Nets {1984} European Workshop on Applications and Theory in Petri Nets, covers the last two years which include the workshop 1983 in Toulouse and the workshop 1984 in Aarhus, selected papers}, Editor = {Rozenberg, Grzegorz and Genrich, Hartmann and Roucairol, G{\'e}rard}, Isbn = {3-540-15204-0}, Pages = {234--258}, Publisher = Springer, Series = LNCS, Title = {The residue of vector sets with applications to decidability problems in {Petri} nets}, Volume = 188, Year = 1985 }

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.