PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2004 | 14 | 1 | 113-121
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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
Rocznik
Tom
14
Numer
1
Strony
113-121
Opis fizyczny
Daty
wydano
2004
otrzymano
2003-04-24
poprawiono
2003-10-03
Twórcy
  • Institute of Computer Engineering and Electronics, University of Zielona Góra, ul. Podgórna 50, 65-246 Zielona Góra, Poland
  • Institute of Computer Engineering and Electronics, University of Zielona Góra, ul. Podgórna 50, 65-246 Zielona Góra, Poland
  • 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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-amcv14i1p113bwm
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.