Wyznaczanie pokrycia sieci Petriego przez SM-komponenty z wykorzystaniem przeszukiwania grafów

• Autorzy: Karatkiewicz A. , Wiśniewski R.

Warianty tytułu

EN

Computation of Petri nets covering by SM-components based on the graph theory

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono nową metodę dekompozycji na składowe automatowe żywych i bezpiecznych sieci Petriego, należących do klasy rozszerzonych sieci swobodnego wyboru (EFC). Metoda polega na przeszukiwaniu grafu sieci, biorąc pod uwagę relację współbieżności pomiędzy miejscami sieci. Przedstawiono i omówiono wyniki wstępnych eksperymentów, które pokazują dużą skuteczność metody względem rozwiązań ogólnie stosowanych, szczególnie w przypadku sieci zawierających wiele miejsc wzajemnie współbieżnych.

EN

In the paper a new method of state machine decomposition of live and safe Petri net that belongs to the Extended Free-Choice class is presented. The method is based on search of the net graph, taking into account concurrency relation between places of the net. The method can be divided into two main steps. In the first one concurrency relation between particular places of the Petri net is computed. Next, the main decomposition process is performed, where subsequent SM-components are calculated. At the first step the method operates on the structure of the net. It is based on the modified algorithm, initially proposed by A.V. Kovalyov in [1]. Such an algorithm permits to find the concurrency relations between places in the Free Choice nets in a polynomial time. Next, the subsequent SM-components are computed. To find each SM-component, a graph-search algorithm is applied. Moreover, the concurrency relation obtained in the first step of proposed method is also taken into account. The method has polynomial computational complexity, unlike most of other methods of such decomposition. It is proved that the first step of an algorithm can be executed in a polynomial time in a case of a Extended Free Choice nets. Furthermore, the graph-search algorithm operates in a linear time, thus the whole decomposition process can be performed in a polynomial time.

Słowa kluczowe

PL

sieci Petriego; dekompozycja sieci Petriego; składowe automatowe; współbieżność; SM-components

EN

Petri nets; decomposition; concurrency

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2012
• Tom: R. 88, nr 8
• Strony: 141--144
• Opis fizyczny: Bibliogr. 16 poz., rys., wykr.

Twórcy

autor

Karatkiewicz A.

autor

Wiśniewski R.

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

Bibliografia

• [1] Kovalyov A.V., Concurrency Relation and Safety Problem for Petri Nets. Proceedings of the International Conference “Application and Theory of Petri Nets”, LNCS, Springer-Verlag, Berlin Heidelberg, 616 (1992)
• [2] Wiśniewska M., Adamski M., Wiśniewski R., Dekompozycja sterowników współbieżnych z zastosowaniem transwersal dokładnych hipergrafu, Pomiary, Automatyka, Kontrola, 57 (2011), nr.8, 851-853
• [3] Banaszak Z., Kuś J., Adamski M., Sieci Petriego. Modelowanie, Sterowanie i Synteza Systemów Dyskretnych, Wydawnictwo Wyższej Szkoły Inżynierskiej, Zielona Góra, 1993
• [4] Murata T., Petri Nets: Properties, Analysis and Applications, Proceedings of th1 IEEE, 77 (1989), n.40
• [5] Tkacz J., Adamski M., Wyznaczanie SM - pokrycia bezpiecznej sieci Petriego metodą komputerowego wnioskowania, Pomiary, Automatyka, Kontrola 2011, 57 (2011), nr.11, 1397-1400
• [6] Wiśniewska M., Dekompozycja systemów dyskretnych z wykorzystaniem hipergrafów, Rozprawa doktorska, Uniwersytet Zielonogórski, Zielona Góra, 2012
• [7] Adamski M., Parallel Controller Implementation using Standard PLD software. FPGAs, Abingdon EE & CS Books, Abingdon, 1991
• [8] Biliński K., Adamski M., Saul J.M., Dagless E.L., Parallel Controller Synthesis from a Petri Net Specification, Proceedings of the European Design Automation Conference EURODAC'94, IEEE Computer Society Press, Grenoble, 1994
• [9] Best E., Structural theory of Petri nets: The free choice hiatus, LNCS, Springer-Verlag, New York, 254 (1987)
• [10] Lasota A., Modelowanie procesów produkcyjnych z wykorzystaniem diagramów aktywności języka UML i sieci Petriego, Rozprawa doktorska, Uniwersytet Zielonogórski, Exit, Zielona Góra, 2012
• [11] Augin M., Boeri F., Andre C., Systematic method of realization of interpreted Petri nets, Digital Processes, 6 (1980), 55-68
• [12] Karatkevich A., Zagadnienia redukcji podsieci automatowych w sieciach Petriego, Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne, 6 (2008), 806-808
• [13] Karatkevich A., Dynamic analysis of Petri net-based discrete systems, Lecture Notes in Control and Information Sciences, Berlin: Springer-Verlag, 356 (2007)
• [14] Ashar P., Devadas S., Newton R.A., A Unified Approach to Decomposition and Re-Decomposition of Sequential Machines, Proceedings of the 27th Design Automation Conference, 1990, 601-606
• [15] De Micheli, G., Synthesis and Optimization of Digital Circuits, McGraw-Hill, New York, NY, 1994
• [16] Zakrevsky A.D., Logical Synthesis of Programmable Schemes, Nauka, Moscow, 1981 (w j. rosyjskim)