# Detection of deadlocks and traps in Petri nets by means of Thelen's prime implicant method

Agnieszka Węgrzyn; Andrei Karatkevich; Jacek Bieganowski

International Journal of Applied Mathematics and Computer Science (2004)

- Volume: 14, Issue: 1, page 113-121
- ISSN: 1641-876X

## Access Full Article

top## Abstract

top## How to cite

topWęgrzyn, Agnieszka, Karatkevich, Andrei, and Bieganowski, Jacek. "Detection of deadlocks and traps in Petri nets by means of Thelen's prime implicant method." International Journal of Applied Mathematics and Computer Science 14.1 (2004): 113-121. <http://eudml.org/doc/207672>.

@article{Węgrzyn2004,

abstract = {A new method of detecting deadlocks and traps in Petri nets is presented. Deadlocks and traps in Petri nets can be represented by the roots of special equations in CNF form. Such equations can be solved by using the search tree algorithm proposed by Thelen. In order to decrease the tree size and to accelerate the computations, some heuristics for Thelen's method are presented.},

author = {Węgrzyn, Agnieszka, Karatkevich, Andrei, Bieganowski, Jacek},

journal = {International Journal of Applied Mathematics and Computer Science},

keywords = {liveness; Petri net; trap; analysis; deadlock},

language = {eng},

number = {1},

pages = {113-121},

title = {Detection of deadlocks and traps in Petri nets by means of Thelen's prime implicant method},

url = {http://eudml.org/doc/207672},

volume = {14},

year = {2004},

}

TY - JOUR

AU - Węgrzyn, Agnieszka

AU - Karatkevich, Andrei

AU - Bieganowski, Jacek

TI - Detection of deadlocks and traps in Petri nets by means of Thelen's prime implicant method

JO - International Journal of Applied Mathematics and Computer Science

PY - 2004

VL - 14

IS - 1

SP - 113

EP - 121

AB - A new method of detecting deadlocks and traps in Petri nets is presented. Deadlocks and traps in Petri nets can be represented by the roots of special equations in CNF form. Such equations can be solved by using the search tree algorithm proposed by Thelen. In order to decrease the tree size and to accelerate the computations, some heuristics for Thelen's method are presented.

LA - eng

KW - liveness; Petri net; trap; analysis; deadlock

UR - http://eudml.org/doc/207672

ER -

## References

top- Barkaoui K. and Minoux M. (1992): A polynomial-time graph algorithm to decide liveness of some basic classes of bounded Petri nets, In: Lecture Notes in Computer Science (K. Jensen, Ed.). - Berlin: Springer-Verlag, Vol. 616, pp. 62-75.
- Best E., Cherkasova L., Desel J. and Esparza J. (1990): Characterisation of home states in free choice systems, In: Semantics for Concurrency (M.Z. Kwiatkowska, M.W. Schields, R.M. Thomas, Eds.). - Proc. Int. BCS-FACS Workshop, Leicester, UK, pp. 16-20, London: Springer.
- Das S. and Khabra N. (1972): Clause-column table approach for generating all the prime implicants of switchingfunctions. - IEEE Trans. Comp., pp. 1239-1246.
- Ezpeleta J., Couvreur J.M. and Silva M. (1993): A new technique for finding a generating family of siphons, traps and st-components. Application to colored Petri Nets, In: Advances in Petri Nets(G. Rozenberg, Eds.). - Berlin: Springer-Verlag, Vol. 674.
- Girault C. and Valk R. (2003): Petri Nets for Systems Engineering. - Berlin: Springer. Zbl1024.68072
- Jiao L., Cheung T.-Y. and Lu W. (2002): Characterizing liveness of Petri nets in terms of siphons. - Proc. 23rd Int. Conf. Applications and Theory of Petri Nets, London: Springer-Verlag, Vol. 2360. Zbl1047.68086
- Kotov V.Ye. (1984): Petri Nets. - Moscow: Nauka, (in Russian). Zbl0606.68052
- Lautenbach K. (1987): Linear algebraic calculation of deadlocks and traps, In: Concurrency and Nets, Advances of Petri Nets (K. Voss, H.J. Genrich and G. Rozenberg, Eds.). -Berlin: Springer-Verlag. Zbl0641.68081
- Lewis R.W. (1995): Programming industrial control systems using IEC1131-3, In: IEE Control Engineering Series, London, Vol. 50.
- Mathony H.-J. (1989): Universal logic design algorithm and its application the synthesis of two-level switching circuits. - IEE Proc., Vol. 136, No. 3, pp. 171-177.
- De Micheli D. (1994): Synthesis and Optimization of Digital Circuits. - New York: McGraw-Hill.
- Silva M. (1985): Las redes de Petri en la Informatica y la Automatica. - Technical Report, MAdrid.
- Murata T. (1989): Petri nets: Properties, analysis and applications. - Proc. IEEE, Vol. 77, No. 4, pp. 541-580.
- Ohta A., Tsuji K. and Hisamura T. (1999): On liveness of extended partially ordered condition nets. -IEICE Trans. Fund. Electron. Commun. Comput. Sci., Vol. E82-A, No. 11, pp. 2576-2578.
- Papadimitriou Ch.H. (1994): Computational Complexity. - Reading, MA: Addison Wesley. Zbl0833.68049
- Peterson J.L. (1981): Petri Net Theory and The Modeling of Systems. - Englewood Cliffs: Prentice-Hall. Zbl0461.68059
- Pottosin Yu.V. (1995): Generating of parallel automata, In: Methods and algorithms of logical design (A.D. Zakrevskij, Ed.). - Institute of Engineering Cybernetics, the Academy of Sciences of Belarus, Minsk, (in Russian), pp. 132-142.
- Reusch B. (1975): Generation of prime implicants from subfunctions and a unifying approach to the covering problem. - IEEE Trans. Comp., Vol. C-24, No. 9, pp. 924-930. Zbl0318.94033
- Schmidt K. (1996a): How to calculate symbolically siphons and traps of algebraic Petri nets. - Techn. Rep. No. A39, Helsinki University of Technology pp. 1-40.
- Schmidt K. (1996b): Siphons and traps for algebraic Petrinets. - Proc. Workshop CSP, Berlin, pp. 157-168.
- Schmidt K. (1997): Characterizing liveness of Petri nets in terms ofsiphons. - Proc. 18th Int. Conf. Application and Theory of Petri Nets, pp. 271-289.
- Sifakis J. (1979): Controle des systemes asynchrones: concepts, proprietes, analyse statique. - I'Universite Scientifique et Medical de Grenoble.
- Tanimoto S., Yamauchi M. and Watanabe T. (1996): Finding minimal siphons in general Petri nets. - IEICE Trans. Fundam. Electron. Commun. Comput. Sci., Vol. E79-A, No. 11, pp. 1817-1824.
- Thelen B. (1988): Investigations of algorithms for computer-aided logic design of digital circuits. - Univ. of Karlsruhe, (in Germany).
- Węgrzyn A. (2003): Symbolic analysis of logical control devices using selected methods of Petri net analysis. - Warsaw Univ. Technol., (in Polish).
- Yamauchi M., Tanimoto S. and Watanabe T. (1996): Finding a minimal siphon containing specified places in a general Petrinet. - IEICE Trans. Fundam. Electron. Commun. Comput. Sci., Vol. E79-A, No. 11, pp. 1825-1828.
- Yamauchi M. and Watanabe T. (1999): Time complexity analysis of the minimal siphon extraction problem of Petri nets. - IEICE Trans. Fundam. Electron. Commun. Comput. Sci., Vol. E82-A, No. 11, pp. 2558-2565.
- Zakrevskij A.D. (1999): Parallel logical control algorithms.- Institute of Engineering Cybernetics, Academy of Sciences of Belarus, Minsk, (in Russian).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.