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

• Autorzy: Agnieszka Węgrzyn , Andrei Karatkevich , Jacek Bieganowski
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

liveness; Petri net; trap; analysis; deadlock

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2004
• Tom: 14
• Numer: 1
• Strony: 113-121

Daty

wydano

2004

otrzymano

2003-04-24

poprawiono

2003-10-03

Twórcy

autor

Agnieszka Węgrzyn

• Institute of Computer Engineering and Electronics, University of Zielona Góra, ul. Podgórna 50, 65-246 Zielona Góra, Poland

autor

Andrei Karatkevich

• Institute of Computer Engineering and Electronics, University of Zielona Góra, ul. Podgórna 50, 65-246 Zielona Góra, Poland

autor

Jacek Bieganowski

• Institute of Computer Engineering and Electronics, University of Zielona Góra, ul. Podgórna 50, 65-246 Zielona Góra, Poland

Bibliografia

• 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.
• 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.
• Kotov V.Ye. (1984): Petri Nets. - Moscow: Nauka, (in Russian).
• 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.
• 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.
• Peterson J.L. (1981): Petri Net Theory and The Modeling of Systems. - Englewood Cliffs: Prentice-Hall.
• 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.
• 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).