Doskonała sieć Petriego w projektowaniu współbieżnych układów sterujących

• Autorzy: Adamski M. , Kołopieńczyk M. , Mielcarek K.

Warianty tytułu

EN

Perfect Petri Net in parallel control circuits

• Języki publikacji: PL

Abstrakty

PL

W artykule wskazano na korzyści płynące z wykorzystania doskonałych bezpiecznych sieci Petriego w projektowaniu współbieżnych układów sterujących. Przedstawiono sposób sprawdzenia, czy sieć Petriego jest siecią doskonałą poprzez analizę jej stanów globalnych i badanie relacji miedzy jej stanami lokalnymi. Potwierdzono, że grafy współbieżności i sekwencyjności między miejscami sieci są grafami doskonałymi. Konsekwencją doskonałości sieci jest możliwość wykorzystania algorytmów o złożoności wielomianowej do jej analizy dynamicznej i statycznej.

EN

This paper is pointing out benefits from application of perfect and safe Petri Nets to design process of parallel control circuits. There is presented a method for verifying the perfectness of Petri Net achieved by analysis of Petri Net global states and relation between Petri Net local states. There is also proved that the concurrency and sequencing graphs of a given Petri Net are perfect. Static and dynamic analysis can be performed using algorithms with polynomial complexity. The presented dependences can also be used to decompose a given Petri Net into components, i.e. state machines, and analyze and verify the project correctness. Petri net analysis is discussed on an example of a real-life object of the beverages mixing system. This paper is divided into five parts. The first section is a brief introduction to issues of perfect and safe Petri Nets. The second section is the theoretical introduction to the subject matter. In the third section an example of perfect Petri nets is presented. In the fourth section the method of constructing the perfect Petri Nets is presented. The last section contains the sum-mary.

Słowa kluczowe

PL

sieć Petriego; sieć doskonała; graf doskonały

EN

Petri net; perfect net; perfect graph

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 6
• Strony: 656--660
• Opis fizyczny: Bibliogr. 17 poz., rys., tab., wzory

Twórcy

autor

Adamski M.

autor

Kołopieńczyk M.

autor

Mielcarek K.

• Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Licealna 9, 65-417 Zielona Góra,

Bibliografia

• [1] Adamski M., Chodań M.: Modelowanie układów sterowania dyskretnego z wykorzystaniem sieci SFC, Wydawnictwo PZ, Zielona Góra, 2000.
• [2] Balakrishnan V. K.: Introductory Discrete Mathematics, Prentice Hall, Englewood Cliffs, 1991.
• [3] Berge C.: Graphs and Hypergraph, North-Hols Mathematical Library, Amsterdam, 1976.
• [4] Chudnovsky M., N. Robertson, P. Seymour, R. Thomas: The strong perfect graph theorem, 2002.
• [5] Cornuéjols G., Cunnigham W. H.: Compositions for perfect graphs, Discrete Mathematics 55 (1985) 245-254.
• [6] Cornuéjols G., Xinming L., Vuškovič K.: A polynomial algorithm for recognizing perfect graphs, Proceeding 44th Annual IEEE Symposium, 2003.
• [7] Coudert O.: Exact Coloring of Real-Life Graphs is Easy, Proc. of the 34th Design Automation Conference DAC, Anaheim, CA, USA, June 1997.
• [8] Deo N.: Graph theory with applications to engineering and computer science, Prentice-Hall Inc., Englewood Cliffs, New Jersey, USA.
• [9] Fehling R.: A Concept of Hierarchical Petri Nets with Building Blocks, In Proceedings of 14th International Conference on Application and Theory of Petri Nets, Vol. 674, Springer-Verlag, 1993.
• [10] Golumbic M. C.: Algorithmic Graph Theory and Perfect Graphs, Courant Institute of Mathematical Science, New York University, Academic Press 1980.
• [11] Kołopieńczyk M.: Application of Address Converter for Decreasing Memory Size of Compositional Mikroprogram Control Unit with Code Sharing, Zielona Góra, 2008.
• [12] Kovalyov A. V.: Concurrency Relation and the Safety Problem for Petri Nets, Institute of Engineering Cybernetics of Belarusian Academy of Science, Minsk 1992.
• [13] Lovász L.: A Characterization of Perfect Graphs, Journal of Combinatorial Theory, 1972.
• [14] Mielcarek K.: Perfect Graphs in Digital Circuits Design, PhD Thesis, University of Zielona Góra, Zielona Góra 2010.
• [15] Murata T.: Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE, Vol. 77, No. 4, 1989.
• [16] Petri C. A.: Kommunikation mit Automaten, Institut für Instrumentelle Mathematik, Schriften des IIM, Nr 3, 1962.
• [17] Valette R.: Etude comparative de deux outils de representation: Grafcet et reseau de Petri, Le Nouvel Automatisme, Decembre 1978.