P-semiflow computation with decision diagrams. (English) Zbl 1242.68175

Franceschinis, Giuliana (ed.) et al., Applications and theory of Petri nets. 30th international conference, PETRI NETS 2009, Paris, France, June 22–26, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02423-8/pbk). Lecture Notes in Computer Science 5606, 143-162 (2009).
Summary: We present a symbolic method for p-semiflow computation, based on zero-suppressed decision diagrams. Both the traditional explicit methods and our new symbolic method rely on Farkas’ algorithm, and compute a generator set from which any p-semiflow for the Petri net can be derived through a linear combination. We demonstrate the effectiveness of four variants of our algorithm by applying them on a suite of Petri net models, showing that our symbolic approach can produce results in cases where the explicit approach is infeasible.
For the entire collection see [Zbl 1165.68011].


68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI


[1] Chiola, G., Franceschinis, G., Gaeta, R., Ribaudo, M.: GreatSPN 1.7: Graphical Editor and Analyzer for Timed and Stochastic Petri Nets. Performance Evaluation 24, 47–68 (1995) · Zbl 0875.68663
[2] Ciardo, G., Jones, R.L., Miner, A.S., Siminiceanu, R.: Logical and stochastic modeling with SMART. Performance Evaluation 63, 578–608 (2006)
[3] Colom, J.M., Silva, M.: Convex geometry and semiflows in P/T nets: A comparative study of algorithms for the computation of minimal p-semiflows. In: Proc. International Conference on Applications and Theory of Petri nets, pp. 74–95 (1989)
[4] Colom, J., Silva, M.: Improving the linearly based characterization of P/T nets. In: Rozenberg, G. (ed.) APN 1990. LNCS, vol. 483, pp. 113–145. Springer, Heidelberg (1991)
[5] Farkas, J.: Theorie der einfachen ungleichungen. Journal für die reine und andgewandte Mathematik 124, 1–27 (1902)
[6] Genrich, H.: Predicate/transition nets. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) APN 1986. LNCS, vol. 254, pp. 207–247. Springer, Heidelberg (1987) · Zbl 0635.68059
[7] Govindarajan, R., Suciu, F., Zuberek, W.M.: Timed Petri net models of multithreaded multiprocessor architectures. In: Proc. Petri Nets and Performance Models, pp. 153–162 (1997)
[8] Graf, S., Steffen, B., Lüttgen, G.: Compositional minimisation of finite state systems using interface specifications. Journal of Formal Aspects of Computing 8(5), 607–616 (1996) · Zbl 0860.68067
[9] Kimura, S., Clarke, E.M.: A parallel algorithm for constructing binary decision diagrams. In: Proc. International Conference on Computer Design, pp. 220–223. IEEE Comp. Soc. Press, Los Alamitos (1990)
[10] Minato, S.-I.: Zero-suppressed BDDs and their applications. Software Tools for Technology Transfer 3, 156–170 (2001) · Zbl 1002.68589
[11] Pastor, E., Roig, O., Cortadella, J., Badia, R.M.: Petri net analysis using boolean manipulation. In: Valette, R. (ed.) ICATPN 1994. LNCS, vol. 815, pp. 416–435. Springer, Heidelberg (1994)
[12] Wan, M., Ciardo, G.: Symbolic state-space generation of asynchronous systems using extensible decision diagrams. In: Nielsen, M., et al. (eds.) SOFSEM 2009. LNCS, vol. 5404, pp. 582–594. Springer, Heidelberg (2009) · Zbl 1206.68104
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.