2013 | OriginalPaper | Chapter
Application of an Exact Transversal Hypergraph in Selection of SM-Components
Authors : Łukasz Stefanowicz, Marian Adamski, Remigiusz Wisniewski
Published in: Technological Innovation for the Internet of Things
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The paper deals with the application of the hypergraph theory in selection of State Machine Components (SM-Components) of Petri nets [1,2].As it is known, Petri nets are widely used for modeling of concurrency processes. However, in order to implement the concurrent automaton, an initial Petri net ought to be decomposed into sequential automata (SM-Components), which can be easily designed as an Finite-State-Machine (FSM) or Microprogrammed Controller [3]. The last step of the decomposition process of the Petri nets is selection of SM-Components. This stage is especially important because it determines the final number of sequential automata. In the article we propose a new idea of SM-Components selection. The aim of the method is reduction of the computational complexity from exponential to polynomial. Such a reduction can be done if the selection hypergraph belongs to the exact transversal hypergraphs (xt-hypergraphs) class. Since the recognition and generation of the first transversal in the xt-hypergraphs are both polynomial, the complete selection process can be performed in polynomial time. The proposed ideas are an extension of the concept presented in [1].The proposed method has been verified experimentally. The conducted investigations have shown that for more than 85% of examined Petri nets the selection process can be done via xt-hypergraphs.