PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Algorytm selekcji wykorzystujący teorię hipergrafów

Treść / Zawartość
Identyfikatory
Warianty tytułu
EN
A selection algorithm based on the hypergraph theory
Języki publikacji
PL
Abstrakty
PL
Artykuł porusza kwestię selekcji określonych elementów zbioru z wykorzystaniem teorii hipergrafów. Przedstawiona została idea wspólnego algorytmu selekcji, w przypadku takich problemów, jak selekcja podsieci automatowych w dekompozycji sieci Petriego, a także selekcja implikantów prostych w procesie miminalizacji funkcji logicznych. Jako bazowy algorytm, wykorzystano metodę transwersal dokładnych, jednocześnie usprawniając ją o alternatywną scieżkę w przypadku, kiedy dany hipergraf selekcji nie należy do klasy hipergrafu transwersal dokładnych. Jak pokazują badania, metoda może być dobrą alternatywą obok wykorzystywanych metod tradycyjnych.
EN
The paper deals with the selection problem based on the hypergraph theory. There is presented an idea of a common selection algorithm for selection of State Machine Components and Prime Implicants. The exact transversal method was used as a baseline algorithm. It was improved by supporting it with an optional path when a given selection hypergraph did not belong to the xt-class (class of the exact transversal hypergraph). In this case, the exact transversal was searched. When it was unsuccessful, the regular transversal was searched. The studies prove that the method allows obtaining the exact solution when the selection hypergraph does not belong to the xt-class, but has an exact transversal. The presented results show that a hypergraph which does not belong to the xt-class may have an exact transversal enabling obtaining a solution which would be as good as the one obtained with the backtracking method. The exact solution was also obtained with the use of an ordinary transversal, which de facto indicated that the regular transversals allowed, in certain cases, obtaining the exact solution. It seems to confirm the aptly determined class of solutions of the proposed improvements. In some cases, the solution contained one extra subnet, but in one tested case, the solution turned out to be much worse than the exact one.
Wydawca
Rocznik
Strony
516--518
Opis fizyczny
Bibliogr. 19 poz.., tab., rys.
Twórcy
  • Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Licealna 9, 65-417 Zielona Góra
  • Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Licealna 9, 65-417 Zielona Góra
autor
  • Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Licealna 9, 65-417 Zielona Góra
Bibliografia
  • [1] Murata T.: Petri nets: properties, analysis and applications, Proceedings of the IEEE 77, pp. 541-580, 1989.
  • [2] Karatkevich A.: Dynamic analysis of Petri net-based discrete systems, Berlin, Springer, 2007.
  • [3] Karatkevich A., Wiśniewski R.: Computation of Petri nets covering by SM-components based on the graph theory, Przegląd Elektrotechniczny, nr 8, s.141-144, 2012.
  • [4] Wiśniewska M.: Application of Hypergraphs in Decomposition of Discrete Systems, Vol. 23 of LNCCS. University of Zielona Góra Press, Zielona Góra, 2012.
  • [5] Stefanowicz Ł., Adamski M., Wiśniewski R.: Application of an Exact Transversal Hypergraph in Selection of SM-Components, IFIP Advanced in Information and Communication Technology, Lisbon, 2013.
  • [6] Either T.: Exact transversal hypergraphs and application to boolean u-functions, Journal of Symbolic Computation 17 (3), pp.215-225, 1994.
  • [7] Wiśniewska M., Wiśniewski R., Adamski M., Halang W.: Application of hypergraphs in microcode length reduction of microprogrammed controllers, Second International Workshop on Nonlinear Dynamics and Synchronization, Smart System Technologies, s.106-109, 2009.
  • [8] Adamski M., Wiśniewska M., Wiśniewski R., Stefanowicz Ł.: Application of hypergraphs to the reduction of the memory size in the Microprogrammed Controllers with Address Converter, Przegląd Elektrotechniczny, nr 8, s.134-136, 2012.
  • [9] Wiśniewski R., Stefanowicz Ł.: Zastosowanie hipergrafów w procesie selekcji implikantów prostych, Pomiary Automatyka Kontrola, Vol.59, nr 11, s.1195-1197, 2013.
  • [10] Coudert O.: Two-Level Logic Minimization: An Overview, Integration Vol. 17, No. 2, s. 97-140, Oct. 1994.
  • [11] McCluskey E. J.: Introduction to the Theory of Switching Circuits, McGraw-Hill, New York, 1965.
  • [12] Kania D.: Układy logiki programowalnej, PWN, Warszawa, 2012.
  • [13] Adamski M., Karatkievich A., Węgrzyn M. (ed.): Design of Embeded Control Systems. NY, Springer Science, 2005.
  • [14] Berge C.: Graphs and Hypergraphs, American Elsevier Pub. Co., 1989.
  • [15] Berge C.: Hypergraphs: Combinatorics of Finite Sets, North-Holland, 1989.
  • [16] Wiśniewski R., Adamski M., Wiśniewska M.: Polynomial algorithm for concurrency hypergraph formulation of free-choice Petri net, Measurement, Automatics, Control, Vol7, pp.650-652, 2012.
  • [17] Kovalyov A.: Concurrency Relations and the Safety Problem for Petri Nets, Application and Theory of Petri Nets, 1992.
  • [18] DeMicheli G.: Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994.
  • [19] Eiter T., Gottlob G.: Identyfying the Minimal Transversals of a Hypergraph and Related Problems, SIAM Journal on Computing, Vol.24, pp. 1278-1304, 1992.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-9a4c6418-1295-4da9-a1aa-4442b1724a07
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.