Zastosowanie teorii hipergrafów w procesie analizy systemów dyskretnych opisanych sieciami Petriego

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

Warianty tytułu

EN

Application of hypergraphs to analysis of discrete-systems described with Petri Nets

• Języki publikacji: PL

Abstrakty

PL

W artykule zaprezentowane zostały nowe metody wspomagające proces analizy systemów dyskretnych opisanych sieciami Petriego. Relacje w prototypowanym systemie dyskretnym są odwzorowane hiper-grafem. Dzięki temu projektowany, wbudowany, rekonfigurowany sterownik logiczny może zostać poddany efektywniejszemu procesowi analizy z wykorzystaniem nowych algorytmów, związanych z traktowanymi łącznie teoriami hipergrafów i sieci Petriego. Wykorzystano między innymi takie procedury jak dopełnienie, dualizm, transwersale, transwersale dokładne oraz kolorowanie hipergrafu. W artykule w sposób nieformalny wykorzystano autorskie twierdzenia, wspomagające cały proces projektowania sterowników. Szczególną uwagę zwrócono na nowe sposoby analizy systemów dyskretnych, opisanych sieciami Petriego, takie jak częściowa weryfikacja poprawności specyfikacji sterownika na podstawie struktury hipergrafu współbieżności oraz zastosowanie transwersal do-kładnych w procesie wyodrębniania powiązanych ze sobą procesów sekwencyjnych.

EN

In the paper application of the hypergraph theory to analysis of discrete-systems described by means of Petri Nets is proposed. The relations between local states are represented by hypergraph vertices whose edges correspond to the global states. Therefore, the analysis of a prototype system can be performed by more effective operations supported by the hypergraph theory as well as the Petri net theory (such as dualism, hypergraph complement, transversals, exact transversals, hypergraph colouring). In the paper the authors propose application of the concurrency hypergraph to the analysis of a discrete-system. Such a structure refers to the traditional concurrency graph, however it keeps information about global states of the analysed system. Moreover, the concurrency hypergraph has some unique properties, which can lead to reduction in the computational complexity of some algorithms of the analysis. All minimal transversals in the concurrency hypergraph are also exact transversals. Therefore, such a hypergraph can be applied also to the decomposition process of a discrete-system, which is described by a Petri Net. After the analysis, a controller described by a Petri Net can be decomposed into concurrent sub-nets (concurrent automata). Each exact transversal of the concurrency hypergraph refers to the concurrent automata. The proposed solution allows significantly reducing the computational complexity to a polynomial. The traditional methods, based on the coloring of a concurrency graph are exponential time algorithms, thus they are defined to be NP-complete.

Słowa kluczowe

PL

hipergraf; transwersala dokładna; sieć Petriego; system dyskretny

EN

hypergraph; exact transversal; Petri net; discrete system

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 8
• Strony: 945--947
• Opis fizyczny: Bibliogr. 16 poz., rys., wzory

Twórcy

autor

Adamski M.

autor

Wiśniewska M.

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

Bibliografia

• [1] De Micheli G.: Synthesis and Optimization of Digital Circuits. McGrawHill, 1994.
• [2] Łuba T.: Synteza układów cyfrowych. Praca zbiorowa pod redakcją prof. Tadeusza Łuby, WKŁ, Warszawa, 2003.
• [3] Adamski M., Węgrzyn M.: Petri nets mapping into reconfigurable logic controllers. Electronics and Telecommunications Quarterly, 2009, Vol. 55, no. 2, s. 157-182.
• [4] Adamski M.: Projektowanie układów cyfrowych systematyczną metodą strukturalną. Wydawnictwo Wyższej Szkoły Inżynierskiej w Zielonej Górze, Zielona Góra, 1990, Monografie 49, ISSN 02397390.
• [5] Adamski M., Karatkevich A., Węgrzyn M. (Red): Design of embedded control systems. New York: Springer, 2005, 267 s.
• [6] Zakrevskij A. D.: Paralel algorithms for logic control. In Russian. Bielorussian Academy of Science Publisher. Minsk, 1999, ISBN 985-6453-26-7.
• [7] Bilinski K., Adamski M., Saul J. M., Dagless E. L.: Petri Net based algorithms for parallel controller synthesis. IEEE Proceedings, Computers and Digital Techniques. No. 141, 1994, pp. 405-412.
• [8] Karatkevich A.: Dynamic Analysis of Petri Net Based Discrete Systems. LNCiS, vol. 356, Springer-Verlag, Berlin 2007.
• [9] David R., Alla H. D. R.: Petri Nets and Grafcet. Tools for modeling discrete event system. London: Prentice Hall, 1992.
• [10] Wiśniewska M.: Zastosowanie dualizmu hipergrafów w dekompozycji równoległej automatów współbieżnych. Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, 2008, nr 6, s. 731-733.
• [11] Berge C.: Graphs and Hypergraph. North-Hols.r Mathematical Library, Amsterdam 1976.
• [12] Eiter T., Gottlob G.: Hypergraph transversal computation and related problems in logic and AI. LNCS, pp. 549-564, Springer, 2002.
• [13] Sapiecha P.: Algorytmy syntezy funkcji i relacji boolowskich w aspekcie metod reprezentacji i kompresji danych. PW, Wydział Elektroniki i Technik Informacyjnych, Warszawa, 1998.
• [14] Tkacz J., Adamski M.: Projektowanie sekwencyjnych układów cyfrowych z wykorzystaniem logiki sekwentów Gentzena, Przegląd Elektrotechniczny, R. 85, nr 7, pp. 196-199, 2009.
• [15] Wiśniewska M.: Redukcja rozmiaru mikroinstrukcji w projektowaniu sterowników mikroprogramowanych, PAK, Nr 8, s. 575-577, 2009.
• [16] Eiter T., Gottlob G., Makino K.: New results on monotone dualization and generating hypergraph transversals. Proc. of the 32th ACM Symp. STOC’02, 14-22, 2002.