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.

Abrégé: Non disponible.

BibTeX enregistrement

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

Copyright Notice

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.