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/