Abstract
P-semiflows are non-negative left anullers of a net's flow matrix. The importance of these vectors lies in their usefulness for analyzing net properties. The concept of minimal p-semiflow is known in the context of Mathematical Programming under the name "extremal direction of a cone". This connection highlights a parallelism between properties found in the domains of P/T nets and Mathematical Programming. The algorithms known in the domain of P/T nets for computing elementary semi-flows are basically a new rediscovery, with technical improvements with respect to type of problems involved, 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, this paper presents two improved algorithms which are more efficient and robust when handling "real-life" Nets.
This is a preview of subscription content, log in via an institution.
Preview
Unable to display preview. Download preview PDF.
References
ALAIWAN H.,MEMMI G.: Algorithmes de Recherche des Solutions Entieres Positives d'un Systeme Lineaire d'Equations Homogenes. Revue Technique-CSF,vol.14, n o 1, Mars, pp. 125–135.
Petri Nets: Central Models and their Properties. Advances in Petri Nets 1986, Proceedings of an Advanced Course, Bad Honnef, September 1986. LNCS 254, Springer Verlag, Berlin.
BALINSKI, M.L.: An Algorithm for Finding all Vertices of Convex Polyhedral Sets. SIAM IX, pp. 72–78.
BRAMS G.W.: Réseaux de Petri. Theorie et pratique, Masson, Paris.
CHERNIKOVA N.V.: Algorithm for Finding a General Formula for the Nonnegative Solutions of a System of Linear Equations, U.S.S.R. Computational Mathematics and Mathematical Physics IV, pp. 151–156.
CHVATAL V.: Linear Programming, W.H. Freeman and Company, New York, 1983.
COLOM J.M.: Métodos de análisis estructural de Redes de Petri basados en Programación Lineal y Geometría Convexa. Tesis Doctoral. Universidad de Zaragoza. June 1989.
DANTZIG G.B.: Linear Programming and Extensions. Princeton University Press.
DINES L.L.: On Positive Solutions of a System of Linear Equations, Annals of Mathematics 28, pp. 386–392.
DUFFIN R.J.: On Fourier's Analysis of Linear Inequality Systems, Mathematical Programming Study 1, American Elsevier Publishing Company, New York, pp. 71–95.
DYER M.E., PROLL L.G.: An Algorithm for Determining All Extreme Points of a Convex Polytope. Math. Programming XII, pp. 81–96.
FARKAS J.: Theorie der einfachen Ungleichungen. In: Journal für die reine und andgewandte Mathematik, 124, pp. 1–27.
FOURIER J.B.J.: Solution d'une Question Particuliere du Calcul des Inegalités. In Oeuvres II, pp. 317–328, Gauthier-Villars, Paris.
GENRICH H.J.: Predicate/Transition Nets. In [APN 87], pp. 207–247.
HADLEY G.: Linear Programming. Addison Wesley, Reading, Massachusetts.
JENSEN K.: Coloured Petri Nets. In [APN 87], pp. 248–299.
KANNAN, R., BACHEM A.: Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix. SIAM J. Comp., vol. 8, pp. 499–507.
KOHLER D.A.: Projections of Convex Polyhedral Sets. Report ORC 67-29, Operations Research Center, University of California at Berkeley.
KRUCKEBERG F., JAXY M.: Mathematical Methods for Calculating Invariants in Petri Nets, Advances in Petri Nets 1987 (Ed. Grzegorz Rozenberg) LNCS 266, Springer Verlag.
LANGFORD C.H: Some Theorems on deducibility.Annals of Mathematics I,28, pp.16–40.
MANAS M., NEDOMA J.: Finding All Vertices of a Convex Polyhedron. Numer. Math. XII, pp.226–229.
MARTINEZ J., SILVA M.: A Simple and Fast Algorithm to Obtain all Invariants of a Generalized Petri Net. Second European Workshop on Application and Theory of Petri Nets, Bad Honnef, September, pp. 411–422.
MARTINEZ J.: Contribución al Análisis y Modelado de Sistemas Concurrentes mediante Redes de Petri. Tesis Doctoral. Universidad de Zaragoza, Octubre 1984.
MATTHEISS T.H.: An Algorithm for Determining Irrelevant Constraints an All Vertices in Systems of Linear Inequalities. Operations Res. 21, pp. 247–260.
MATHEISS T.H.,RUBIN D.S.: A Survey and Comparison of Methods for Finding all Vertices of Convex Polyhedral Sets Mathematics of Ops. Res., Vol.5, No.2, May, pp.167–185.
MEMMI G: Fuites et semiflots dans les réseaux de Petri. Thése de Docteur Ingenieur. Univ. Pierre et Marie Curie, Paris VI, Paris, Decembre.
MOTZKIN T.S.: Beitrage zur Theorie der Linearen Ungleichungen, Doctoral Thesis, University of Zurich.
MURTY K.G.: Solving the Fixed Charge Problem by Ranking the Extreme Points. Operations Res. XVI, pp. 268–279.
MURTY K.G.: Adjacency on Convex Polyhedra, SIAM. Rev. XIII, pp. 377–386.
SILVA M.: Las Redes de Petri en la Automática y la Informática. Editorial AC, Madrid.
SILVA M., COLOM J.M.: On the Computation of Structural Synchronic Invariants in P/T nets, Advances in Petri Nets 1988 (g. Rozenberg, ed.), LNCS 340, Springer Verlag, Berlin, pp 386–417.
TOUDIC J.M.: Algorithmes d'analyse structurelle de réseaux de Petri. These 3éme Cycle, Université Pierre et Marie Curie, Paris VI, Octobre.
TREVES N.: Le Calcul d'Invariants dans le Réseaux de Petri a Predicats Transitions Unaires. Thése de Docteur de 3éme cycle, Univ. de Paris-Sud, Centre d'Orsay, Novembre, Paris.
WILLIAMS H.P.: Fourier-Motzkin Elimination Extension to Integer Programming Problems. Journal of Combinatorial theory (A) 21, pp. 118–123.
WILLIAMS H.P.: Fourier's Method of Linear Programming and its Dual, American Mathematical Monthly, Nov. 1986, pp. 681–695.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Colom, J.M., Silva, M. (1991). Convex geometry and semiflows in P/T nets. A comparative study of algorithms for computation of minimal p-semiflows. In: Rozenberg, G. (eds) Advances in Petri Nets 1990. ICATPN 1989. Lecture Notes in Computer Science, vol 483. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-53863-1_22
Download citation
DOI: https://doi.org/10.1007/3-540-53863-1_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53863-9
Online ISBN: 978-3-540-46369-6
eBook Packages: Springer Book Archive