Geodesic
A method for bi-decomposition of partial Boolean functions
Prikladnaâ diskretnaâ matematika, no. 1 (2020), pp. 108-116.

Voir la notice de l'article provenant de la source Math-Net.Ru

A method for bi-decomposition of incompletely specified (partial) Boolean functions is suggested. The problem of bi-decomposition is reduced to the problem of two-block weighted covering a set of edges of a graph of rows orthogonality of a ternary or binary matrix that specify a given function, by complete bipartite subgraphs (bicliques). Each biclique is assigned in a certain way with a set of arguments of the given function, and the weight of a biclique is the cardinality of this set. According to each of bicliques, a Boolean function is constructed whose arguments are the variables from the set, which is assigned to the biclique. The obtained functions form a solution of the bi-decomposition problem.
Keywords: partial Boolean function, cover problem, complete bipartite subgraph.
Mots-clés : bi-decomposition 
@article{PDM_2020_1_a8,
     author = {Yu. V. Pottosin},
     title = {A method for bi-decomposition of partial {Boolean} functions},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {108--116},
     publisher = {mathdoc},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2020_1_a8/}
}
TY  - JOUR
AU  - Yu. V. Pottosin
TI  - A method for bi-decomposition of partial Boolean functions
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2020
SP  - 108
EP  - 116
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2020_1_a8/
LA  - en
ID  - PDM_2020_1_a8
ER  - 
%0 Journal Article
%A Yu. V. Pottosin
%T A method for bi-decomposition of partial Boolean functions
%J Prikladnaâ diskretnaâ matematika
%D 2020
%P 108-116
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2020_1_a8/
%G en
%F PDM_2020_1_a8
Yu. V. Pottosin. A method for bi-decomposition of partial Boolean functions. Prikladnaâ diskretnaâ matematika, no. 1 (2020), pp. 108-116. http://geodesic.mathdoc.fr/item/PDM_2020_1_a8/

[1] Perkowski M. A., Grygiel S., A Survey of Literature on Functional Decomposition, Version IV, Technical Report, Portland State University, Department of Electrical Engineering, Portland, USA, 1995, 188 pp.

[2] Cortadella J., “Timing-driven logic bi-decomposition”, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 22:6 (2003), 675–685 | DOI

[3] Mishchenko A., Steinbach B., Perkowski M., “An algorithm for bi-decomposition of logic functions”, Proc. 38th Ann. Design Automation Conf. (Las Vegas, NV, USA, ACM, June 2001), 103–108

[4] Chang S.-C., Marek-Sadowska M., Hwang T., “Technology mapping for TLU FPGA's based on decomposition of binary decision diagrams”, IEEE Trans. Computer-Aided Design, 15:10 (1996), 1226–1235 | DOI

[5] Bibilo P. N., Decomposition of Boolean Functions Based on Solving Logical Equations, Belaruskaya Navuka, Minsk, 2009, 211 pp. (in Russian)

[6] Zakrevskij A. D., “On a special kind decomposition of weakly specified Boolean functions.”, Second Intern. Conf. CAD DD'97 (Minsk, Republic of Belarus, November 12–14, 1997), v. 1, NAS of Belarus, Institute of Engineering Cybernetics, Minsk, 1997, 36–41 | MR

[7] Cheng D., Xu X., “Bi-decomposition of logical mappings via semi-tensor product of matrices”, Automatica, 49:7 (2013), 1979–1985 | DOI | MR | Zbl

[8] Choudhury M., Mohanram K., “Bi-decomposition of large Boolean functions using blocking edge graphs”, IEEE/ACM Intern. Conf. ICCAD (San Jose, CA, USA), IEEE Press, 2010, 586–591

[9] Fišer P., Schmidt J., “Small but nasty logic synthesis examples”, Proc. IWSBP'8 (Freiberg, Germany, Freiberg University of Mining and Technology, Sept. 2008), 183–190 | Zbl

[10] Steinbach B., Posthoff C., “Vectorial bi-decomposition for lattices of Boolean functions”, Further Improvements in the Boolean Domain, ed. B. Steinbach, Cambridge Scholars Publishing, 2018, 175–198 | MR

[11] Pottosin Yu. V., Shestakov E. A., “Decomposition of a system of partial Boolean functions with the help of covering a graph by complete bipartite subgraphs”, Proc. 2nd Conf. “New Information Technologies in the Study of Discrete Structures”, UrS RAS, Yekaterinburg, 1998, 185–189 (in Russian)

[12] Zakrevskij A. D., Pottosin Yu. V., Cheremisinova L. D., Combinatorial Algorithms of Discrete Mathematics, TUT Press, Tallinn, 2008, 193 pp.

[13] Pottosina S., Pottosin Yu., Sedliak B., “Finding maximal complete bipartite subgraphs in a graph”, J. Appl. Math., 1:1 (2008), 75–81 | MR