Geodesic
Finding the subsets of variables of~a~partial~Boolean~function which~are~sufficient for~its~implementation in~the~classes defined by predicates
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 110-126

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

Given a class $K$ of partial Boolean functions and a partial Boolean function $f$ of $n$ variables, a subset $U$ of its variables is called sufficient for the implementation of $f$ in $K$ if there exists an extension of $f$ in $K$ with arguments in $U$. We consider the problem of recognizing all subsets sufficient for the implementation of $f$ in $K$. For some classes defined by relations, we propose the algorithms of solving this problem with complexity of $O(2^nn^2)$ bit operations. In particular, we present some algorithms of this complexity for the class $P_2^*$ of all partial Boolean functions and the class $M_2^*$ of all monotone partial Boolean functions. The proposed algorithms use the Walsh–Hadamard and Möbius transforms. Bibliogr. 21.
Keywords: partial Boolean function, sufficient subset of variables, Walsh–Hadamard transform
Mots-clés : Möbius transform. 
@article{DA_2020_27_1_a5,
     author = {N. G. Parvatov},
     title = {Finding the subsets of variables {of~a~partial~Boolean~function} which~are~sufficient for~its~implementation in~the~classes defined by predicates},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {110--126},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_1_a5/}
}
TY  - JOUR
AU  - N. G. Parvatov
TI  - Finding the subsets of variables of~a~partial~Boolean~function which~are~sufficient for~its~implementation in~the~classes defined by predicates
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 110
EP  - 126
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_1_a5/
LA  - ru
ID  - DA_2020_27_1_a5
ER  - 
%0 Journal Article
%A N. G. Parvatov
%T Finding the subsets of variables of~a~partial~Boolean~function which~are~sufficient for~its~implementation in~the~classes defined by predicates
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 110-126
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_1_a5/
%G ru
%F DA_2020_27_1_a5
N. G. Parvatov. Finding the subsets of variables of~a~partial~Boolean~function which~are~sufficient for~its~implementation in~the~classes defined by predicates. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 110-126. http://geodesic.mathdoc.fr/item/DA_2020_27_1_a5/