Silva, M.; Colom, J. M. On the computation of structural synchronic invariants in P/T nets. (English) Zbl 0668.68070 Advances in Petri nets, APN, Proc. 8th Eur. Workshop, Zaragoza/Spain 1987, Lect. Notes Comput. Sci. 340, 386-417 (1988). [For the entire collection see Zbl 0658.00014.] Inside synchrony theory, this paper deals with a computation of structural synchronic invariants. It is based on the state equation of the place/transition (P/T) net and on linear programming theory. The approach is conceptually very simple, generaland computationally very efficient. It is said to be a general approach in the sense that instead of single transition, subsets of transitions are directly taken into account. Computationally it is very efficient because the linear programming problem is known to be of polynomial complexity. Two transition subsets are in a given synchronic relation if the corresponding synchronic invariant is bounded; for all conflict- resolution strategies, synchronic relations characterize the existence or non-existence of firing dependencies. As a by-product of the proposed approach, a full algebraic characterization of structural synchronic relations (i.e. independent of the initial marking) is obtained. Cited in 13 Documents MSC: 68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) 90C05 Linear programming 68Q25 Analysis of algorithms and problem complexity Keywords:place/transition net; P/T nets; structural synchronic invariants; state equation; linear programming; polynomial complexity; conflict-resolution; firing dependencies; algebraic characterization Citations:Zbl 0658.00014 PDFBibTeX XML