*For the most recent entries see the
Petri Nets Newsletter.*

## Semilinearity of the Reachability Set is Decidable for Petri Nets.

Hauschildt, Dirk
*Bericht des Fachbereichs Informatik, Nr. 146*, pages 1-154 pp..
FBI-HH-B-146/90 --- Hamburg, Germany: Universität,
1990.

Abstract:
The author presents an algorithm deciding for a given Petri net, whether
its reachability set is semilinear. If so, the algorithm computes a
semilinear representation of the set. Otherwise it produces two semilinear
estimations --- Actually, the setting of the problem considered in this
paper is more general. It is based on the so-called extended reachability
relation ER. A linear set L is used to select a portion of ER; inside this
portion, the information that one is interested in is specified by a
linear mapping. The algorithm computes an upper estimate SL^{+}
and a lower estimate SL^{-} of this set. They are optimal in the
sense that the dimension of SL^{+} / SL^{-} is as small as
possible.

Keywords:
decidability (of the) semilinearity (of the) reachability set; extended
reachability relation.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*