Dekompozycja sterowników współbieżnych z zastosowaniem transwersal dokładnych hipergrafu

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

Warianty tytułu

EN

Exact transversals in decomposition of Petri Nets into concurrent subnets

• Języki publikacji: PL

Abstrakty

PL

W artykule zaprezentowany został nowatorski sposób dekompozycji cyfrowych sterowników współbieżnych opisanych z wykorzystaniem sieci Petriego na podsieci typu automatowego. W proponowanym rozwiązaniu relacje pomiędzy miejscami sieci Petriego określone za pomocą hipergrafu współbieżności. W odróżnieniu od dotychczas stosowanych rozwiązań, w artykule zaproponowano autorską koncepcję wyznaczania zbiorów niewspółbieżnych, która bazuje na obliczeniu transwersal dokładnych w hipergrafie współbieżności.

EN

In the paper a new decomposition method of a control system into concurrent automata is presented. The control unit is described as a Petri Net which is further decomposed into concurrent subnets. The main idea of the proposed method is application of exact transversals to the decomposition algorithm. Contrary to the traditional solutions, the authors propose the application of a concurrency hypergraph instead of a standard concurrency graph. The concurrent subnets are found by calculation of exact transversals in the hypergraph. The selection of concurrent automata is also performed with application of exact transversals. Such a solution allows achieving the optimal results (the fewest number of concurrent automata). The proposed concurrency hypergraph has some unique properties. First of all, it is defined to be an exact hypergraph. Therefore, each exact transver-sal in such a hypergraph refers to the concurrent automata. Moreover, all minimal transversals of the hypergraph are also exact transversals. Finally, computation and selection of all exact transversals can be performed in polynomial-time, and this is the most important advantage of the proposed method. The traditional solutions are based on the coloring of a concurrency graph, thus the complexity is NP-complete. All steps that are required in order to perform the decomposition of a controller described by a Petri Net are shown. The proposed method is compared with the traditional solution. Finally, the preliminary results of experiments are presented and discussed.

Słowa kluczowe

PL

hipergraf; transwersala dokładna; sieć Petriego; dekompozycja sieci Petriego; podsieci współbieżne typu automatowego

EN

hypergraph; exact transversal; Petri net; decomposition of a Petri Net into concurrent subnets automata

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

Twórcy

autor

Wiśniewska M.

autor

Adamski M.

autor

Wiśniewski R.

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

Bibliografia

• [1] David R., Alla H.: Petri Nets & Grafcet. Tools for modelling discrete event systems, Prentice Hall, New York, 1992.
• [2] Adamski M., Karatkievich A., Węgrzyn M. (ed.): Design of Embeded Control Systems. NY, Springer Science, 2005.
• [3] 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.
• [4] Kubale M., Obszarski P., Piwakowski K.: Kolorowanie hipergrafów. Zeszyty Naukowe Politechniki Śląskiej, No. 143, pp. 83-90, 2006.
• [5] Berge C.: Graphs and Hypergraph. North-Hols.r Mathematical Library, Amsterdam 1976.
• [6] Eiter T., Gottlob G.: Hypergraph transversal computation and related problems in logic and AI. LNCS, pp. 549-564, Springer, 2002.
• [7] Knuth D.: Dancing Links, Stanford University, 2000,http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz