Heuristics for Thelen's Prime Implicant Method

• Autorzy: Bieganowski J. , Karatkevich A.
• Języki publikacji: EN

Abstrakty

EN

Thelen's algorithm is an efficient method for generation of the prime implicants of a Boolean function represented in CNF. In the paper new heuristics are presented, allowing to accelerate the algorithm. Experimental analysis of their effects is performed.

Słowa kluczowe

EN

Boolean functions; CNF; prime implicants; search tree

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2005
• Tom: Vol. 14
• Strony: 125--135
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Bieganowski J.

• Institute of Computer Engineering and Electronics, ul. Podgórna 50, 65-246 Zielona Góra

autor

Karatkevich A.

• Institute of Computer Engineering and Electronics, ul. Podgórna 50, 65-246 Zielona Góra

Bibliografia

• [1] Brayton R.K. et al.; VIS: A System for Verification and Synthesis, in: The Proceedings of the Conf. on Computer-Aided Verification, August 1996, Springer Verlag, 1102, pp. 332–334.
• [2] Coudert O., Madre J.K.; New Ideas for Solving Covering Problems, Design Automation Conference, 1995, pp. 641–646.
• [3] Coudert O., Madre J.K., Fraisse H.; A New Viewpoint on Two-Level Logic Minimization, Design Automation Conference, 1993, pp. 625–630.
• [4] Karatkevich A.; On Algorithms for Decyclisation of Oriented Graphs, in: Proceedings of the International Workshop DESDes’01, Zielona Góra, Poland, 2001, pp. 35–40.
• [5] Mathony H.J.; Universal logic design algorithm and its application the synthesis of two-level switching circuits, IEE Proceedings, 136,3, 1989, pp. 171–177.
• [6] Mathony H.J.; Algorithmic Design of Two-Level and Multi-Level Switching Circuits, (in German), PhD thesis, ITIV, Univ. of Karlsruhe, 1988.
• [7] McGeer P.C. et al.; Espresso-Signature: A New Exact Minimizer for Logic Functions, Design Automation Conference, 1993, pp. 618–624.
• [8] De Micheli D.; Synthesis and Optimization of Digital Circuits, Stanford Univ., McGraw-Hill, Inc., 1994.
• [9] Nelson R.; Simplest Normal Truth Functions, Journal of Symbolic Logic, 20,2,1955, pp. 105–108.
• [10] Rudell R., Sangiovanni-Vincentelli A.; Multiple-valued Minimization for PLA Optimization, IEEE Transactions on CAD/ICAS, Sept. 1987, CAD-6, 5, 1987, pp. 727–750.
• [11] Rytsar B., Minziuk V.; The Set-theoretical Modification of Boolean Functions Minimax Covering Method, in: Proceedings of the International Conference TCSET’2004, Lviv–Slavsko, Ukraine, 2004, pp. 46–48.
• [12] Thelen B.; Investigations of algorithms for computer-aided logic design of digital circuits, (in German), PhD thesis, ITIV, Univ. of Karlsruhe, 1981.
• [13] Węgrzyn A., W¸egrzyn M.; Symbolic Verification of Concurrent Logic Controllers by Means Petri Nets, in: Proceedings of the Third International Conference CAD DD’99, Minsk, Belarus, 1999, pp. 45–50.
• [14] Węgrzyn A., Karatkevich A., Bieganowski J.; Detection of deadlocks and traps in Petri nets by means of Thelen’s prime implicant method, AMCS, 14,1, 2004, pp. 113–121.