Autorski system wspomagający proces dekompozycji sieci Petriego na podsieci typu automatowego

• Autorzy: Wiśniewska M.

Warianty tytułu

EN

CAD system for automatic decomposition of Petri Nets

• Języki publikacji: PL

Abstrakty

PL

W referacie przedstawiono autorski system komputerowy wspomagający proces dekompozycji sieci Petriego na podsieci typu automatowego. System sterujący zostaje opisany za pomocą sieci Petriego, na podstawie której określany jest graf lub hipergraf współbieżności. Macierz incydencji hipergrafu współbieżności stanowi dane wejściowe systemu Hippo. Aplikacja oferuje przeprowadzenie dekompozycji z zastosowaniem operacji bazujących na teorii hipergrafów różnymi metodami i umożliwia wybór najlepszej z nich.

EN

The dedicated CAD system Hippo for automatic decomposition of Petri Nets into concurrent automata is presented. At the beginning the reachability graph is calculated for the Petri Net which may be easily represented by a concurrency graph or a hypergraph. Such structures are input for main decomposition process. There are several methods for decomposition of Petri Nets. The most popular one is based on the colouring of the concurrency graph, however recently, a few new algorithms based on hypergraph theory have appeared. Contrary to a concurrency graph, application of a concurrency hypergraph to the decomposition of Petri Net enables using new and fast methods. The solution can be found by colouring of a concurrency hypergraph, calculating its complement or finding exact transversals. Especially, the last method is most interesting, because it allows reducing the computational complexity to a polynomial. In the paper the decomposition process is presented in detail. There are several ways of decomposition presented (based on colouring graphs/hypergraphs), calculating hypergraph complement or finding its exact transversals. Each of the presented method was implemented in Hippo. The decomposition process is automated. As the input of the Hippo system, a description of a concurrency graph or hypergraph is required. Based on this structure and a selected decomposition method, Hippo finds and prints results. The obtained results are presented in graphical and text form.

Słowa kluczowe

PL

hipergraf; transwersala dokładna; system Hippo wspomagający proces dekompozycji sieci Petriego

EN

hypergraph; hypergraph transversal; CAD system Hippo for automatic decomposition of Petri Nets based on hypergraphs

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 8
• Strony: 948--950
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Wiśniewska M.

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

Bibliografia

• [1] Valette R.: Comparative Study of Switching Representation Tool with GRAFCET and Petri Nets. Nouv. Autom, Vol. 23, nr 12, str. 337-382.
• [2] David R., Alla H.: Petri Nets & Grafcet. Tools for modelling discrete event systems, Prentice Hall, New York, 1992.
• [3] Blanchard M.: Comprendre, maitriser et appliquer le GRAFCET, Cepadues Editions, 1979.
• [4] Wiśniewska M., Wiśniewski R., Adamski M.: Zastosowanie transwersali hipergrafów w minimalizacji pojemności pamięci systemów dyskretnych. Pomiary, Automatyka, Kontrola - 2010, Vol. 56, nr 7, s. 777-779.
• [5] Wiśniewska M.: Redukcja rozmiaru mikroinstrukcji w projektowaniu sterowników mikroprogramowanych. PAK, Nr 8, s. 575-577, 2009.
• [6] Wiśniewska M., Wiśniewski R., Adamski M., Halang W.: Application of hypergraphs in microcode lenght reduction of microprogrammed controllers. Second International Workshop on Nonlinear Dynamics and Sychronization – INDS’09. Klagenfurt, Austria, ss. 106-109, 2009.
• [7] Wiśniewska M., Adamski M.: Dekompozycja systemów dyskretnych poprzez zastosowanie hierarchicznej redukcji krawędzi hipergrafów. Pomiary, Automatyka, Kontrola - 2008, Vol. 54, nr 8, s. 517-519.
• [8] Wiśniewska M., Adamski 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.
• [9] Wiśniewska M., Wiśniewski R., Adamski M.: Usage of hypergraph theory in BSW4-0104-0043decomposition of concurrent automata. PAK, nr 7, s. 66-68, 2007.
• [10] Berge C.: Graphs and Hypergraph. Amsterdam: North-Hols.r Mathematical Library, 1976.
• [11] Eiter T., Gottlob G.: Hypergraph transversal computation and related problems in logic and AI. LNCS, pp. 549-564, Springer, 2002.
• [12] Aho A. V., Hopcroft J. E., Ullman J. D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.
• [13] Wiśniewska M., Wiśniewski R.: Zastosowanie kolorowania hipergrafów w procesie dekompozycji równoległej automatów współbieżnych, Metody Informatyki Stosowanej - 2010, nr 2, s. 151.
• [14] Adamski M., Wiśniewska M.: Dekompozycja równoległa automatów współbieżnych z wykorzystaniem hipergrafów. Pomiary Automatyka Kontrola - 2006, nr 6, wyd. spec., s. 8-10.