MIN-Fakultät Fachbereich Informatik Theoretische Grundlagen der Informatik

# Bibliographie

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

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.

Kurzfassung: Bisher nicht verfügbar.

### BibTeX-Eintrag



@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.},
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
}