Wielomianowy algorytm wyznaczania hipergrafu współbieżności w sieciach Petriego swobodnego wyboru

• Autorzy: Wiśniewski R. , Wiśniewska M. , Adamski M.

Warianty tytułu

EN

A polynomial algorithm to compute the concurrency hypergraph in Petri nets

• Języki publikacji: PL

Abstrakty

PL

W referacie zaproponowano metodę umożliwiającą określenie strukturalnej relacji współbieżności w sieciach Petriego swobodnego wyboru (Free Choice). Algorytm znajduje miejsca wzajemnie współbieżne na podstawie struktury sieci oraz miejsc oznaczonych markerem startowym. W odróżnieniu od istniejących algorytmów, proponowana metoda znajduje wszystkie miejsca wzajemnie współbieżne, wyznaczając hipergraf współbieżności. Przeprowadzone badania eksperymentalne potwierdzają bardzo wysoką skuteczność proponowanej metody.

EN

In the paper a new algorithm of concurrency hypergraph computation is presented. The main aim of the proposed method is computation of a concurrency hypergraph in the polynomial time. The algorithm input is specified by the Petri net that belongs to the Free Choice subclass. Based on the net structure, the method outputs the concurrency relations between all places in the net. Particular relations are stored by the concurrency hypergraph instead of the concurrency graph, which is currently practiced. The hypergraph permits to store information about relations between all places in the net. In case of the concurrency graph it is limited to relations between pairs of places. Therefore, application of the concurrency hypergraph seems to be more intuitive and natural. The algorithm bases on the traditional solutions, however particular concurrency relation may contain more than two places which is not possible in currently known methods. The proposed solution is especially valuable in combination with the method presented in [1, 2] and permits to find the subsequent SM-Components in the polynomial time. The algorithm was experimentally verified. The method was compared with the traditional solution, where all maximal cliques in the concurrency graph were computed. The obtained results proved very high effectiveness of the proposed algorithm, which was always better than methods based on the graph theory. We have also noticed that the effectiveness increases drastically with the number of places and transitions in the Petri net.

Słowa kluczowe

PL

sieć Petriego; hipergraf współbieżności; dekompozycja

EN

Petri net; concurrency hypergraph; decomposition

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2012
• Tom: R. 58, nr 7
• Strony: 650--652
• Opis fizyczny: Bibliogr. 11 poz., rys., tab.

Twórcy

autor

Wiśniewski R.

autor

Wiśniewska M.

autor

Adamski M.

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

Bibliografia

• [1] Wiśniewska M.: Dekompozycja systemów dyskretnych z wykorzystaniem hipergrafów. Rozprawa doktorska, Uniw. Zielonogórski, 2011.
• [2] Wiśniewska M., Adamski M., Wiśniewski R.: Dekompozycja sterowników współbieżnych z zastosowaniem transwersal dokładnych hipergrafu. Pomiary, Automatyka, Kontrola 2011, Vol. 57, nr 8, s. 851-853.
• [3] Murata T.: Petri Nets: Properties, Analysis and Applications. Proceedings of IEEE, Vol. 77, pp. 548-580, 1989.
• [4] Yakovlev A., Gomes L., Lavagno L. (Ed.), Hardware Design and Petri Nets. Kluver Academic Publishers, Boston, 2000.
• [5] Karatkevich A.: Dynamic analysis of Petri net-based discrete systems. Lecture Notes in Control and Information Sciences, 356, Berlin: Springer-Verlag 2007.
• [6] Adamski M.: Projektowanie układów cyfrowych systematyczną metodą strukturalną, Monografie 49, Wydawnictwo Wyższej Szkoły Inżynierskiej w Zielonej Górze, Zielona Góra, 1990.
• [7] Bubacz P.: Kodowanie stanów wewnętrznych współbieżnego matrycowego rekonfigurowalnego sterownika logicznego. Rozprawa doktorska, Uniwersytet Zielonogórski 2009.
• [8] Tkacz J., Adamski M.: Wyznaczanie SM - pokrycia bezpiecznej sieci Petriego metodą komputerowego wnioskowania. Pomiary, Automatyka, Kontrola 2011, Vol. 57, nr 11, s. 1397-1400.
• [9] Kovalyov A., Esparza J.: A polynomial algorithm to compute the concurrency relation of free-choice signal transition graphs. In Prof. of the International Workshop on Discrete Event Systems, WODES’96, pages 1-6, Edinburgh, 1996. The Institution of Electrical Engineers.
• [10] Rudell R. L.: Logic Synthesis for VLSI Design. Rozprawa doktorska, EECS Department, University of California, Berkeley 1989.
• [11] Berge C.: Graphs and Hypergraph. Amsterdam: North-Holland Pub. Co.; American Elsevier Pub. Co., Amsterdam, New York 1976.