Algorytm selekcji wykorzystujący teorię hipergrafów

• Autorzy: Stefanowicz Ł. , Wiśniewski R. , Adamski M.

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.

Słowa kluczowe

PL

selekcja; podsieci automatowe; implikanty proste; hipergraf; hipergraf transwersal dokładnych; transwersala; transwersala dokładna

EN

selection; State Machine Components; SMCs; prime implicants; hypergraph; transversal; exact transversal

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2014
• Tom: R. 60, nr 7
• Strony: 516--518
• Opis fizyczny: Bibliogr. 19 poz.., tab., rys.

Twórcy

autor

Stefanowicz Ł.

• Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Licealna 9, 65-417 Zielona Góra

autor

Wiśniewski R.

• Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Licealna 9, 65-417 Zielona Góra

autor

Adamski M.

• 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.