Publikace detail

Complexity Analysis for Petri Net-Based State Space Generation

Autoři: Ibl Martin

Rok: 2013

Druh publikace: článek ve sborníku

Název zdroje: System approaches '13: Systems thinking and global problems of the world

Název nakladatele: Oeconomica

Místo vydání: Praha

Strana od-do: 108-113

Tituly:

Jazyk	Název	Abstrakt	Klíčová slova
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;

Vyhledávání

Přihlášení pro studenty

Přihlášení pro zaměstnance

Publikace detail

Ústavy

Pracoviště

Jak nás najdete?

Služby

Často hledáte