Publication detail

Complexity Analysis for Petri Net-Based State Space Generation

Authors: Ibl Martin

Year: 2013

Type of publication: článek ve sborníku

Name of source: System approaches '13: Systems thinking and global problems of the world

Publisher name: Oeconomica

Place: Praha

Page from-to: 108-113

Titles:

Language	Name	Abstract	Keywords
cze	Analýza algoritmů generování stavového prostoru petri sítí	Jednou z nejdůležitějších součástí systémového myšlení, jsou prostředky, pomocí nichž lze zachytit analyzovaných systém v určité formě (obrázku, diagramu). Jedním z takovýchto prostředků jsou Petri sítě, které umožňuje zachytit a analyzovat složité systémy, které se vyznačují souběžností, či nedeterminstičností. Jednou z hlavních nevýhod využívání Petri sítí k modelování a analýze reálných problémů spočívá převážně v exponenciální složitosti (stavová exploze), která komplikuje analýzu u rozsáhlejších modelů. Problematika Petri sítí je spojena s řadou skutečností týkajících se složitosti a dokazatelnosti specifických vlastností, které dále slouží pro potřeby verifikačních či výkonnostních analýz. Analýzou samotné složitosti těchto vlastností je možné zefektivnit výše zmíněné operace (verifikační a výkonnostní analýza) a zároveň poskytnout prostor pro rozšíření problematiky týkající se algoritmické složitosti příbuzných oborů (např. teorie hromadné obsluhy). Tato práce se zabývá analýzou algoritmů pro generování stavového prostoru Petri sítí. Konkrétně jde o popis a porovnání ?běžného? přístupu, který spočívá v bezpaměťovém generování stavů s nutností ověřovat unikátnost každého stavu a generování založené na principu dynamického programování, které umožňuje výrazně zefektivnit časovou náročnost výpočtu. Samotná komparace těchto dvou přístupů je provedena jak na bázi teoretické, tak praktické (vzorový příklad). Z teoretického hlediska je analyzována časová a prostorová složitost zmíněných algoritmů a z praktického hlediska jsou tyto principy prezentovány na ukázkovém příkladu.	Petri sítě; Složitost; Analýza;
eng	Complexity Analysis for Petri Net-Based State Space Generation	One of the most important parts of system thinking are the means by which is possible to capture the analysed system in some form (diagram, picture etc.). One of such means are Petri Nets, which allows to capture and analyse complex systems characterized by concurrency or non-determinism. One of the main disadvantages of the use of Petri Nets for modelling and analysing real problem lies mainly in exponential complexity (state explosion), which complicates the analysis of larger models. Issues of Petri Nets are associated with a number of facts related to the complexity and provability of specific properties that are also used for the purpose of verification and performance analysis. Analysis of the complexity of these properties can make more effective the above operations (verification and performance analysis) and also provide space for expansion of issues related to algorithmic complexity of the related disciplines (e.g. queuing theory). This paper analyses the algorithms for state space generation of Petri Nets. Specifically, the description and comparison of the "common" approach, which consists in generating memory-free states with the need to verify the uniqueness of each state and generating based on the principle of dynamic programming, which allows to significantly streamline a time-consuming calculation. From a theoretical perspective is analysed time and space complexity of these algorithms.	Petri Nets; Complexity; Analysis;

Search

Login for students

Login for employees

Publication detail

Map

Services

Popular Links