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/

[1] O. I. Golubeva, “Construction of permissible functions and their application for fault tolerance”, Proc. 2019 Int. Sib. Conf. Control Communications (Tomsk, Russia, Apr. 18–20, 2019), TUSUR, Tomsk, 2019, 1–5

[2] A. A. Voronenko, “On a decomposition method for recognizing membership in invariant classes”, Discrete Math. Appl., 12:6 (2002), 607–614 | DOI | MR | Zbl

[3] S. N. Selezneva, “Constructing polynomials for functions over residue rings modulo a composite number in linear time”, Computer science Theory and applications, Lect. Notes Comput. Sci., 7353, Springer, Heidelberg, 2012, 302–313 | DOI | MR | Zbl

[4] V. B. Alekseev, N. R. Emel'yanov, “A method for constructing fast algorithms in k-valued logic”, Math. Notes, 38:1 (1985), 595–600 | DOI | MR | Zbl

[5] V. B. Alekseev, “Stepwise bilinear algorithms and recognition of completeness in k-valued logics”, Soviet Math. (Izv. VUZ), 32:7 (1988), 31–42 | MR | Zbl

[6] V. B. Alekseev, “Logical semirings and their usage for construction of quick algorithms”, Moscow Univ. Math. Bull., 52:1 (1997), 22–28 | MR | Zbl

[7] N. G. Parvatov, “Generating sufficient sets for partial Boolean functions”, Vestn. Tomsk. Gos. Univ., Suppl., 2007, no. 23, 44–48

[8] V. N. Sachkov, Combinatorial Methods of Discrete Mathematics, Nauka, M., 1977

[9] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977 | MR | Zbl

[10] C. K. Rushforth, “Fast Fourier-Hadamard decoding of orthogonal codes”, Inform. Control, 15:1 (1969), 33–37 | DOI | Zbl

[11] A. A. Malyutin, “Fast correlation decoding of some subsets of words of the first-order Reed-Muller code”, Discrete Math. Appl., 2:2 (1992), 155–158 | DOI | MR

[12] Yu. D. Karyakin, “Fast correlation decoding of Reed-Muller codes”, Probl. Peredachi Inform., 23:2 (1987), 40–49 | MR | Zbl

[13] N. N. Tokareva, “Generalizations of bent functions: A survey of publications”, J. Appl. Ind. Math., 5:1 (2011), 110–129 | DOI | MR

[14] L. Weisner, “Abstract theory of inversion of finite series”, Trans. Amer. Math. Soc., 38 (1935), 474–484 | DOI | MR

[15] P. Hall, “The Eulerian functions of a group”, Q. J. Math., 7 (1936), 134–151 | DOI

[16] G. C. Rota, “On the foundations of combinatorial theory: I. Theory of Möbius functions”, Z. Wahrscheinlichkeitstheor. Verw. Geb., 2 (1964), 340–368 | DOI | MR | Zbl

[17] R. P. Stanley, Enumerative combinatorics, v. 1, Camb. Stud. Adv. Math., 49, Camb. Univ. Press, New York, 1997 | MR | Zbl

[18] N. G. Parvatov, “On recognizing of properties of discrete functions by Boolean circuits”, Vestn. Tomsk. Gos. Univ., Suppl., 2005, no. 14, 233–236

[19] A. Schönhage, V. Straßen, “Schnelle Multiplikation großer Zahlen”, Computing, 7 (1971), 281–292 (German) | DOI | MR | Zbl

[20] M. Fürer, “Faster integer multiplication”, Proc. 39th Annu. ACM Symp. Theory Comput. (San Diego, CA, USA, June 11–13, 2007), ACM, New York, 2007, 57–66 | MR | Zbl

[21] A. De, P. P. Kurur, C. Saha, R. Saptharishi, “Fast integer multiplication using modular arithmetic”, Proc. 40th ACM Symp. Theory Comput. (Victoria, Canada, May 17–20, 2008), ACM, New York, 2008, 499–506 ; SIAM J. Comput., 42:2 (2013), 685–699 | MR | Zbl | DOI | MR | Zbl