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.