Application of an Exact Transversal Hypergraph in Selection of SM-Components - Technological Innovation for the Internet of Things Access content directly
Conference Papers Year : 2013

Application of an Exact Transversal Hypergraph in Selection of SM-Components

Łukasz Stefanowicz
  • Function : Author
  • PersonId : 976773
Marian Adamski
  • Function : Author
  • PersonId : 976774
Remigiusz Wisniewski
  • Function : Author
  • PersonId : 976775


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.
Fichier principal
Vignette du fichier
978-3-642-37291-9_27_Chapter.pdf (4 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01348761 , version 1 (25-07-2016)





Łukasz Stefanowicz, Marian Adamski, Remigiusz Wisniewski. Application of an Exact Transversal Hypergraph in Selection of SM-Components. 4th Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Apr 2013, Costa de Caparica, Portugal. pp.250-257, ⟨10.1007/978-3-642-37291-9_27⟩. ⟨hal-01348761⟩
41 View
149 Download



Gmail Facebook X LinkedIn More