Analiza współbieżnych systemów dyskretnych: uparte zbiory i symulacja współbieżna

• Autorzy: Karatkevich A.

Warianty tytułu

EN

Analysis of Parallel Discrete Systems: Persistent Sets and Concurrent Simulation

• Konferencja: Konferencja INFORMATYKA - SZTUKA CZY RZEMIOSŁO, Złotniki Lubańskie, 19-22 czerwca 2006
• Języki publikacji: PL

Abstrakty

PL

Tematem pracy jest problem analizy współbieżnych systemów dyskretnych, które mogą być opisane sieciami Petriego. Ogólnym podejściem do analizy, omawianym w artykule, jest symulacja optymalna, która pozwala sprawdzać właściwości sieci poprzez konstruowanie zredukowanej przestrzeni osiągalności. Dwie znane metody takiej analizy bazują na tak zwanych "upartych zbiorach" oraz na współbieżnej symulacji. W pracy przedstawiono wykorzystanie tych idei w ramach jednej metody. Omówione są też możliwości i zalety połączenia takiej metody z wykorzystaniem dekompozycji.

EN

This paper is focused on problem of analysis of parallel discrete systems, which can be described by Petri nets. The general analysis approach considered in the paper is optimal simulation, allowing checking properties of the system by constructing reduced state spaces. Two well-known methods of such analysis are based on persistent sets and concurrent simulation, correspondingly. Here we discuss possibility of combination between those methods and describe an algorithm using both ideas. Combination with decomposition approach is also discussed.

Słowa kluczowe

PL

współbieżne systemy dyskretne; sieci Petriego; symulacja; eksploracja stanów

EN

parallel discrete system; Petri nets; simulation; state exploration

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2006
• Tom: R. 52, nr 6 bis
• Strony: 20--22
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Karatkevich A.

• Instytut Informatyki i Elektroniki, Uniwersytet Zielonogórski,

Bibliografia

• [1] Adamski M., Skowroński Z.: Interpretowane sieci Petriego – model formalny w zintegrowanym projektowaniu mikroprocesorowych systemów sprzętowo-programowych, PAK 2/3, 2003, 17-20.
• [2] Ferrarini L.: An Incremntal Approach to Logic Controller Design with Petri Nets, IEEE Transactions on System, Man, and Cybernetics, Vol. 22, No. 3, 1992, 461-474.
• [3] Heiner M.: Petri Net Based System Analysis Without State Explosion, in Proceedings of. High Performance Computing’98, Boston, April 1998, 394-403.
• [4] Janicki R., Koutny M.: Using Optimal Simulations to Reduce Reachability Graphs, in Proceedings of the 2nd International Conference CAV’90, 166-175, Springer 1991.
• [5] Janicki R., Lauer P. E., Koutny M., Devillers R.: Concurrent and Maximally Concurrent Evolution of Non-Sequential Systems, Theoretical Computer Science, 43, 1986, 213-238.
• [6] Karatkevich A.: Optimal Simulation of ?-Nets, in: Proceedings of the Polish-German Symposium SRE’2000, Zielona Góra, 2000, 217-222.
• [7] Karatkevich A., Zakrevskij A.: Analysis of Petri Nets by Means of Concurrent Simulation, in Proceedings of the International Conference PARELEC, Warsaw, September 2002, 87-91.
• [8] Murata T.: Petri Nets: Properties, Analysis and Applications, Proceedings of IEEE, vol. 77, no. 4, April 1989, pp. 548-580.
• [9] Valmari A.: State of the Art Report: Stubborn Sets, Petri Net Newsletter, April 1994, 6-14.
• [10] Wolper P., Godefroid P.: Partial-Order Methods for Temporal Verification, in Proceedings of the 4th International Conference CONCUR’93, 233-246, Springer 1993.
• [11] Zakrevskij A., Karatkevich A., Adamski M.: A Method of Analysis of Operational Petri Nets, in Proceedings of the 8th International Conference ACS’2001, 449-460, Kluwer Academic Publishers, 2002.
• [12] Закревский А. Д.: Параллельные алгоритмы логического управления, ИТК АНБ, 1999.