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

Abstract

top
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.

How to cite

top

Wę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
  1. 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. 
  2. 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. 
  3. Das S. and Khabra N. (1972): Clause-column table approach for generating all the prime implicants of switchingfunctions. - IEEE Trans. Comp., pp. 1239-1246. 
  4. 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. 
  5. Girault C. and Valk R. (2003): Petri Nets for Systems Engineering. - Berlin: Springer. Zbl1024.68072
  6. 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
  7. Kotov V.Ye. (1984): Petri Nets. - Moscow: Nauka, (in Russian). Zbl0606.68052
  8. 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
  9. Lewis R.W. (1995): Programming industrial control systems using IEC1131-3, In: IEE Control Engineering Series, London, Vol. 50. 
  10. 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. 
  11. De Micheli D. (1994): Synthesis and Optimization of Digital Circuits. - New York: McGraw-Hill. 
  12. Silva M. (1985): Las redes de Petri en la Informatica y la Automatica. - Technical Report, MAdrid. 
  13. Murata T. (1989): Petri nets: Properties, analysis and applications. - Proc. IEEE, Vol. 77, No. 4, pp. 541-580. 
  14. 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. 
  15. Papadimitriou Ch.H. (1994): Computational Complexity. - Reading, MA: Addison Wesley. Zbl0833.68049
  16. Peterson J.L. (1981): Petri Net Theory and The Modeling of Systems. - Englewood Cliffs: Prentice-Hall. Zbl0461.68059
  17. 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. 
  18. 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
  19. 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. 
  20. Schmidt K. (1996b): Siphons and traps for algebraic Petrinets. - Proc. Workshop CSP, Berlin, pp. 157-168. 
  21. Schmidt K. (1997): Characterizing liveness of Petri nets in terms ofsiphons. - Proc. 18th Int. Conf. Application and Theory of Petri Nets, pp. 271-289. 
  22. Sifakis J. (1979): Controle des systemes asynchrones: concepts, proprietes, analyse statique. - I'Universite Scientifique et Medical de Grenoble. 
  23. 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. 
  24. Thelen B. (1988): Investigations of algorithms for computer-aided logic design of digital circuits. - Univ. of Karlsruhe, (in Germany). 
  25. Węgrzyn A. (2003): Symbolic analysis of logical control devices using selected methods of Petri net analysis. - Warsaw Univ. Technol., (in Polish). 
  26. 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. 
  27. 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. 
  28. Zakrevskij A.D. (1999): Parallel logical control algorithms.- Institute of Engineering Cybernetics, Academy of Sciences of Belarus, Minsk, (in Russian). 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.