Zastosowanie kolorowania hipergrafów w procesie dekompozycji równoległej automatów współbieżnych

• Autorzy: Wiśniewska M. , Wiśniewski R.
• Języki publikacji: PL

Abstrakty

PL

W referacie zapręzentowano metodę dekompozycji sieci Petriego na podsieci typu automatowego, opartą o kolorowanie hipergrafu osiągalności. Zaprezentowano szczegółowe wyniki przeprowadzonych badań, w których proponowane rozwiązanie porównano z klasycznymi metodami opartymi o kolorowanie grafów osiągalności. Wyniki eksperymentów pokazały, że prezentowany algorytm jest znacznie szybszy od dotychczas stosowanych rozwiazań (nawet 1600 razy w przypadku sieci zawierających 200 miejsc).

EN

In the article a decomposition method of concurrent automata is presented. The main advantage of the presented method is the availability of hypergraph theory usage instead of graph one. Hypergraph contains all information about the relations between hyperedges while in graph all cliques have to be found. Furthermore, the process of finding concurrent automata can be more effective because of hypergraph coloring usage. The computation of the hypergraph coloring is less complex than adequate graph coloring. Let us point out that the results of both solutions, either hypergraph and graph coloring are here the same.

Słowa kluczowe

PL

dekompozycja sieci Petriego; hipergraf; kolorowanie hipergrafu; równoległość automatów

EN

PetriNet decomposition; hypergraph; hypergraph colloring; concurrent automata

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2010
• Tom: nr 2 (23)
• Strony: 151--157
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Wiśniewska M.

autor

Wiśniewski R.

• Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki

Bibliografia

• [1] Adamski M., Karatkievich A., Węgrzyn M. (ed.) Design of Embeded Control Systems. NY, Springer Science, 2005
• [2] Bilinski K., Adamski M., Saul J.M., Dagless E.L. Petri-net-based algorithms for parallel-controller synthesis. IEE Proceedings - Computers and Digital Techniques, 1994, Vol. 141, no 6, s. 405-412
• [3] Berge C. Graphs and Hypergraphs. North-Hollands Mathematical Library, Amsterdam 1976
• [4] David R., Alla H. Petri Nets & Grafcet. Tools for modelling discrete event systems. Prentice Hall, New York, 1992
• [5] Kubale M., Obszarski P., Piwakowski K. Kolorowanie hipergrafów. Zeszyty Naukowe Politechniki Śląskiej 143 (2006), 83-90
• [6] Łuba T. Synteza układów cyfrowych. WKŁ, Warszawa 2003
• [7] Valette R. Comparative Study of Switching Representation Tool with GRAFCET and Petri Nets. Nouv. Autom., Vol. 23, nr. 12, str. 337-382
• [8] Wiśniewska M, Wiśniewski R., Adamski M. Usage of hypergraph theory in decomposition of concurrent automata. PAK,. 2007, nr 7, s. 66-68