Email this article Universal Functions for Classes of Bilinear and Polylinear Boolean Functions
- Authors: Voronenko A.A.1
-
Affiliations:
- Faculty of Computational Mathematics and Cybernetics, Moscow State University and Moscow Institute of Physics and Technology
- Issue: Vol 29, No 4 (2018)
- Pages: 449-452
- Section: III. Informatics
- URL: https://journal-vniispk.ru/1046-283X/article/view/247795
- DOI: https://doi.org/10.1007/s10598-018-9423-4
- ID: 247795
Cite item
Open Access
Access granted
Subscription Access
Abstract
The following problem is considered: specify a Boolean function of n variables such that every bilinear (polylinear) function is reduced, on a certain number of tuples of the specified function, to a unique bilinear (polylinear) function that is identical with the specified function on these tuples. We show that this is feasible for bilinear functions and for polylinear functions with a fixed number of parentheses k, starting with some n , and we can restrict the analysis to a sequence of functions with definition domain of cardinality O(n).
About the authors
A. A. Voronenko
Faculty of Computational Mathematics and Cybernetics, Moscow State University and Moscow Institute of Physics and Technology
Author for correspondence.
Email: dm6@cs.msu.ru
Russian Federation, Moscow
Supplementary files
