In: Proceedings of the 10th International Conference on Application and Theory of Petri Nets, 1989, Bonn, Germany, pages 74-95. 1989.
Also: Universidad de Zaragoza, departamento de ingenieria electrica e informatica, Research Report 89-01, January 1989.
Also in: Rozenberg, G.: Lecture Notes in Computer Science, Vol. 483; Advances in Petri Nets 1990, pages 79-112. Berlin, Germany: Springer-Verlag, 1991.
Abstract: P-semiflows are nonnegative left annullers of a net's flow matrix. The concept of minimal p-semiflow is known in the context of mathematical programming under the name `extremal direction of a cone'. The algorithms known in the domain of P/T nets for computing elementary semi-flows are basically improvements of the basic Fourier-Motzkin method. One of the fundamental problems of these algorithms is their complexity. Various methods and rules for mitigating this problem are examined. As a result, the paper presents two improved algorithms which are more efficient and robust when handling `real-life' nets.
Keywords: convex geometry (and) semiflows (in) place/transition net(s); minimal p-semiflows computation; Fourier-Motzkin method; complexity reduction.