Finding the subsets of variables of a partial Boolean function which are sufficient for its implementation in the classes defined by predicates. (Russian. English summary) Zbl 1491.68090
Summary: 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.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 06E30 | Boolean functions |
| 68W40 | Analysis of algorithms |
Keywords:
partial Boolean function; sufficient subset of variables; Walsh-Hadamard transform; Möbius transformReferences:
| [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 · Zbl 1088.68614 · doi:10.4213/dm266 |
| [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 · Zbl 1360.68956 · doi:10.1007/978-3-642-30642-6_28 |
| [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 · Zbl 0616.03011 · doi:10.1007/BF01137475 |
| [5] | V. B. Alekseev, “Stepwise bilinear algorithms and recognition of completeness in k-valued logics”, Soviet Math. (Izv. VUZ), 32:7 (1988), 31-42 · Zbl 0713.03011 |
| [6] | V. B. Alekseev, “Logical semirings and their usage for construction of quick algorithms”, Moscow Univ. Math. Bull., 52:1 (1997), 22-28 · Zbl 0914.94026 |
| [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 · Zbl 0369.94008 |
| [10] | C. K. Rushforth, “Fast Fourier-Hadamard decoding of orthogonal codes”, Inform. Control, 15:1 (1969), 33-37 · Zbl 0192.56301 · doi:10.1016/S0019-9958(69)90601-9 |
| [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 · Zbl 0787.94024 · doi:10.1515/dma.1992.2.2.155 |
| [12] | Yu. D. Karyakin, “Fast correlation decoding of Reed-Muller codes”, Probl. Peredachi Inform., 23:2 (1987), 40-49 · Zbl 0636.94021 |
| [13] | N. N. Tokareva, “Generalizations of bent functions: A survey of publications”, J. Appl. Ind. Math., 5:1 (2011), 110-129 · Zbl 1448.94311 · doi:10.1134/S1990478911010133 |
| [14] | L. Weisner, “Abstract theory of inversion of finite series”, Trans. Amer. Math. Soc., 38 (1935), 474-484 · JFM 61.1027.02 · doi:10.1090/S0002-9947-1935-1501822-0 |
| [15] | P. Hall, “The Eulerian functions of a group”, Q. J. Math., 7 (1936), 134-151 · JFM 62.0082.02 · doi:10.1093/qmath/os-7.1.134 |
| [16] | G. C. Rota, “On the foundations of combinatorial theory: I. Theory of Möbius functions”, Z. Wahrscheinlichkeitstheor. Verw. Geb., 2 (1964), 340-368 · Zbl 0121.02406 · doi:10.1007/BF00531932 |
| [17] | R. P. Stanley, Enumerative combinatorics, v. 1, Camb. Stud. Adv. Math., 49, Camb. Univ. Press, New York, 1997 · Zbl 0889.05001 |
| [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) · Zbl 0223.68007 · doi:10.1007/BF02242355 |
| [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 · Zbl 1179.68198 |
| [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 · Zbl 1271.68247 · doi:10.1137/100811167 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
