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.
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/