DocumentCode :
186506
Title :
Application of comparability graphs in decomposition of Petri nets
Author :
Wisniewski, Rafael ; Karatkevich, Andrei ; Adamski, Mariusz ; Kur, Daniel
Author_Institution :
Univ. of Zielona Gora, Zielona Gora, Poland
fYear :
2014
fDate :
16-18 June 2014
Firstpage :
216
Lastpage :
220
Abstract :
In the article we present a new algorithm of Petri net decomposition into State Machine Components (SMCs). The idea bases on the application of the comparability graph theory. The comparability graphs are classified as a subclass of the perfect graphs and have unique properties. If a graph belongs to the comparability class, many problems (like graph coloring, maximal clique problem) can be solved in polynomial time. Therefore, if the sequentiality graph of a Petri net belongs to comparability class, the whole decomposition process turns to be polynomial. The preliminary experiments have demonstrated the effectiveness of the proposed idea. Over 90% of concurrency and sequentiality graphs of tested benchmarks belong to the comparability class. The efficiency is even higher if the Petri net class is reduced to the EFC (Extended Free-Choice).
Keywords :
Petri nets; computational complexity; finite state machines; EFC; Petri net decomposition; SMC; comparability graph theory; extended free-choice; polynomial time; state machine components; Benchmark testing; Color; Computational complexity; Concurrent computing; Petri nets; Polynomials; Unified modeling language;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Human System Interactions (HSI), 2014 7th International Conference on
Conference_Location :
Costa da Caparica
Type :
conf
DOI :
10.1109/HSI.2014.6860478
Filename :
6860478
Link To Document :
بازگشت