RDNF Oriented Analytics to Random Boolean Functions
DOI:
https://doi.org/10.51408/1963-0098Keywords:
Boolean function, Hypercube, Complexity, Asymptotic, Reduced disjunctive normal formAbstract
Dominant areas of computer science and computation systems are intensively linked to the hypercube-related studies and interpretations. This article presents some transformations and analytics for some example algorithms and Boolean domain problems. Our focus is on the methodology of complexity evaluation and integration of several types of postulations concerning special hypercube structures. Our primary goal is to demonstrate the usual formulas and analytics in this area, giving the necessary set of common formulas often used for complexity estimations and approximations. The basic example under considered is the Boolean minimization problem, in terms of the average complexity of the so-called reduced disjunctive normal form (also referred to as complete, prime irredundant, or Blake canonical form). In fact, combinatorial counterparts of the disjunctive normal form complexities are investigated in terms of sets of their maximal intervals. The results obtained compose the basis of logical separation classification algorithmic technology of pattern recognition. In fact, these considerations are not only general tools of minimization investigations of Boolean functions, but they also prove useful structures, models, and analytics for constraint logic programming, machine learning, decision policy optimization and other domains of computer science.
References
Yu. I. Zhuravlev, “Set-Theoretical methods of algebra of logic, Problemi Kibernetiki, vol. 8, pp. 544, 1962.
O. Lupanov and S. Yablonsky, Discrete Mathematics and Mathematical Problems of Cybernetics, Moscow, Nauka, 1974.
A. I. Kitov and N. A. Krinitsky, Electronic Computers, Moscow: USSR Academy of Sciences, 1958.
Yu. L. Vasiliev, “Difficulties of minimization of Boolean functions based on universal approaches”, Soviet Math. Dokl., vol. 171, no. 1, pp. 1316, 1966.
V. Glagolev, “Some estimates of disjunctive normal forms in the algebra of logic, Problems of Cybernetics, Nauka, Moscow, vol. 19 pp. 7594, 1967.
A. A. Sapozhenko, “Mathematical properties of almost all functions of algeΘbra of logic”, Discrete analysis, vol. 10, pp. 91119, 1967.
O. B. Lupanov, “Ob odnom metode sinteza skhem, In: Izv. VUZ (Radiofizika), vol. 1, no.1, pp. 120140, 1958.
L. H. Aslanyan, “On a recognition method, based on partitioning of classes by the disjunctive normal forms”, Kibernetika, vol. 5 pp. 103110, 1975.
L. H. Aslanyan, “Recognition algorithm with logical separators”, Collection of Works on Mathematical Cybernetics, Computer Center, AS USSR, Moscow, pp. 116131, 1976.
L. Aslanyan and J. Castellanos, “Logic based Pattern Recognition - Ontology content (1)”, Inf. Tech. and Applicat. (IJ ITA), vol. 1, pp. 206210, 2007.
L. Aslanyan and V. Ryazanov, “Logic based Pattern Recognition - Ontology content (2)”, Inf. Theories and Applicat, vol. 15, no. 4, pp. 314318, 2008.
L. Aslanyan, H.Sahakyan, H.-D. Gronau and P. Wagner, Constraint satisfaction problems on specific subsets of the n-dimensional unit cube”, Proc. IEEE 10th Int. Comp. Sci. and Infor. Technol. (CSIT), Yerevan, Armenia, pp. 4752, 2015.
L. Aslanyan and H. Sahakyan, “The splitting technique in monotone recognition”, Discrete Applied Mathematics, vol. 216, pp. 502512, 2017.
G. Putzolu and F. Mileto,“Average values of quantaties appearing in Boolean function minimization”, IEEE EC-13, vol. 2, pp. 8792, 1964.
G. Putzolu and F. Mileto, “Average values of quantaties appearing in multiple output Boolean minimization”, IEEE EC-14, vol. 4, pp. 542552, 1965.
L. H. Aslanyan, “On complexity of reduced disjunctive normal form of partial Boolean functions. I.”, Proceedings, Natural Sciences, Yerevan State University, vol. 1, pp. 1118, 1974.
L. H. Aslanyan, “On complexity of reduced disjunctive normal form of partial Boolean functions. II”, Proceedings, Natural Sciences, Yerevan State University, vol. 3, pp. 1623, 1974.
M. Skoviera. “Average values of quantities appearing in multiple output Boolean minimization”, Computers & Artificial Intelligence, vol. 5, pp. 321334, 1986.
E. Toman, “An upper bound for the average length of a dizjunktive normal form of a random Boolean function”, Computers & Artificial Intelligence, vol. 2, pp. 1317, 1983.
K. Weber, “Prime Implicants of Random Boolean Functions”, Journal of Information Processes and Cybernetics, vol. 19, pp. 449458, 1983.
D. Gardy, “Random Boolean expressions”, Computational Logic and Applications, vol. 5, pp. 136, 2005.
J. Boyar, R. Peralta and D. Pochuev, “On the multiplicative complexity of Boolean functions over the basis (and,mod2,1)”, Theoretical Computer Science, vol. 235, no. 1, pp. 43–57, 2000.
X. Gong and J. Socolar, “Quantifying the complexity of random Boolean networks”, In: arXiv:1202.1540v3 [nlin.CG] 26 May 2012.
P. Hrubes”, On the complexity of computing a random Boolean funtion over the reals”, Electronic Colloquium on Computational Complexity Report, no. 36, pp. 111, 2000.
G. Sosa-Gomez, O. Paez-Osuna, O. Rojas, P. Lui del Angel Rodriguez, H. Kanarek and E. J. Madarro-Capo, ”Con-struction of Boolean Functions from Hermitian Codes”, Mathematics, MDPI 10.899, pp. 116, 2022.
Chaubal Siddhesh Prashant, Complexity Measures of Boolean Functions and their Applications, Faculty of the Graduate School of The University of Texas at Austin 2020.
P. Erdos, “Graph theory and probability”, Canad. J. Math, vol. 11, pp. 3438, 1959.
J. Spencer and P. Erdos, Probabilistic Methods in Combinatorics, Moscow: Mir, 1963.
L. H. Aslanyan, “On implementation of reduced disjunctive normal form in the problem of extension of partial Boolean functions”, Junior Researcher, Natural Sciences, Yerevan State University, vol. 20, no. 2, pp. 6575, 1974.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Levon H. Aslanyan, IrinaA.Arsenyan, Vilik M. Karakhanyan and Hasmik A. Sahakyan
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
