|
This article is cited in 3 scientific papers (total in 3 papers)
Computational Methods in Discrete Mathematics
A method for bi-decomposition of partial Boolean functions
Yu. V. Pottosin United Institute of Informatics Problems National Academy of Sciences of Belarus, Minsk, Belarus
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.
Keywords:
partial Boolean function, bi-decomposition, cover problem, complete bipartite subgraph.
Citation:
Yu. V. Pottosin, “A method for bi-decomposition of partial Boolean functions”, Prikl. Diskr. Mat., 2020, no. 47, 108–116
Linking options:
https://www.mathnet.ru/eng/pdm698 https://www.mathnet.ru/eng/pdm/y2020/i1/p108
|
Statistics & downloads: |
Abstract page: | 125 | Full-text PDF : | 47 | References: | 23 |
|