EN|RU
English version: Journal of Applied and Industrial Mathematics, 2018, 12:3, 426-441 |
![]() |
Volume 25, No 3, 2018, P. 126-151 UDC 519.714.7
Keywords: minimization of Boolean functions, complexity, extent, domination, independent family of sets. DOI: 10.17377/daio.2018.25.601 Igor P. Chukhrov 1 Received 24 November 2017 References[1] Yu. L. Vasil’ev and V. V. Glagolev, Metric properties of disjunctive normal forms, in Diskretnaya matematika i matematicheskie voprosy kibernetiki (Discrete Mathematics and Mathematical Problems of Cybernetics), Vol. 1, pp. 99–148, Nauka, Moscow, 1974.[2] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982. [3] A. A. Evdokimov, Maximal length of circuit in a unitary $n$-dimensional cube, Mat. Zametki, 6, No. 3, 309–319, 1969. Translated in Math. Notes Acad. Sci. USSR, 6, No. 3, 642–648, 1969. [4] Yu. I. Zhuravlyov, Algorithms for constructing minimal disjunctive normal forms of Boolean functions, in Diskretnaya matematika i matematicheskie voprosy kibernetiki (Discrete Mathematics and Mathematical Problems of Cybernetics), Vol. 1, pp. 67–98, Nauka, Moscow, 1974. [5] V. B. Kudryavtsev and A. E. Andreev, On algorithm complexity, Fundam. Prikl. Mat., 15, No. 3, 135–169, 2009. Translated in J. Math. Sci., 168, No. 1, 89–122, 2010. [6] Yu. V. Maksimov, Realization of Boolean functions with a bounded number of zeros in the class of disjunctive normal forms, Zh. Vychisl. Mat. Mat. Fiz., 53, No. 9, 1569–1588, 2013. Translated in Comput. Math. Math. Phys., 53, No. 9, 1391–1409, 2013. [7] A. V. Panov, Algorithms using first-order neighborhoods for minimization of Boolean functions, Zh. Vychisl. Mat. Mat. Fiz., 53, No. 9, 1589–1600, 2013. Translated in Comput. Math. Math. Phys., 53, No. 9, 1410–1420, 2013. [8] A. A. Sapozhenko and I. P. Chukhrov, Boolean function minimization in the class of disjunctive normal forms, Itogi Nauki Tekh., Ser. Teor. Veroyatn., Mat. Stat., Teor. Kibern., 25, 68–116, 1987. Translated in J. Sov. Math., 46, No. 4, 2021–2052, 1989. [9] I. P. Chukhrov, Estimates of the number of minimal disjunctive normal forms for the belt function, in Metody diskretnogo analiza v issledovanii funktsional’nykh sistem (Methods of Discrete Analysis in Functional Systems Research), Vol. 36, pp. 74–92, Inst. Mat. SO AN SSSR, Novosibirsk, 1981. [10] I. P. Chukhrov, On complexity measures of complexes of faces in the unit cube, Diskretn. Anal. Issled. Oper., 20, No. 6, 77–94, 2013. Translated in J. Appl. Ind. Math., 8, No. 1, 9–19, 2014. [11] I. P. Chukhrov, Proof of covering minimality by generalizing the notion of independence, Diskretn. Anal. Issled. Oper., 24, No. 2, 87–106, 2017. Translated in J. Appl. Ind. Math., 11, No. 2, 193–203, 2017. [12] O. Coudert and T. Sasao, Two-level logic minimization, in Logic Synthesis and Verification, pp. 1–27, Kluwer Acad. Publ., Netherlands, 2002 (Springer Int. Ser. Eng. Comput. Sci., Vol. 654). [13] C. Umans, T. Villa, and A. L. Sangiovanni-Vincentelli, Complexity of two-level logic minimization, IEEE Trans. CAD Integr. Circuits Syst., 25, No. 7, 1230–1246, 2006. |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|