Abstract:
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.
\Bibitem{Pot20}
\by Yu.~V.~Pottosin
\paper A method for bi-decomposition of partial Boolean functions
\jour Prikl. Diskr. Mat.
\yr 2020
\issue 47
\pages 108--116
\mathnet{http://mi.mathnet.ru/pdm698}
\crossref{https://doi.org/10.17223/20710410/47/9}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000520869800007}
Linking options:
https://www.mathnet.ru/eng/pdm698
https://www.mathnet.ru/eng/pdm/y2020/i1/p108
This publication is cited in the following 4 articles:
Yu. V. Pottosin, “Implementation of a System of Incompletely Specified Boolean Functions in a Circuit of Two-Input Gates by Means of Bi-Decomposition”, J. Comput. Syst. Sci. Int., 63:2 (2024), 298
Yu. V. Pottosin, “Implementation of a system of incompletely specified Boolean functions in a circuit of two-input gates by means of bi-decomposition”, Teoriâ i sistemy upravleniâ, 2024, no. 4, 65
Yu. V. Pottosin, “Synthesis of combinational circuits by means of bi-decomposition of Boolean functions”, PDM, 2023, no. 60, 95–105
Yu. V. Pottosin, “A heuristic method for bi-decomposition of partial Boolean functions”, Informatika (Minsk), 17:3 (2020), 44
Citation in format AMSBIB
Contact us: