|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2020, Number 4, Pages 51–53
(Mi vmumm4341)
|
|
|
|
Short notes
On irreduceability of Boolean functions with respect to commutative associative operation
G. V. Safonov, G. V. Bokov, V. B. Kudryavtsev Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
The paper is focused on decomposition of Boolean functions on the form $f_1\circ\ldots\circ f_m$, where $\circ$ is a commutative associative operation and $f_1,\ldots,f_m$ are Boolean functions with fewer arguments. For each commutative associative operation, we define necessary and sufficient conditions for the absence of such a decomposition and find the related complexity class.
Key words:
Boolean functions, commutative associative operations, decomposition, complexity.
Received: 11.09.2019
Citation:
G. V. Safonov, G. V. Bokov, V. B. Kudryavtsev, “On irreduceability of Boolean functions with respect to commutative associative operation”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2020, no. 4, 51–53; Moscow University Mathematics Bulletin, 75:4 (2020), 169–171
Linking options:
https://www.mathnet.ru/eng/vmumm4341 https://www.mathnet.ru/eng/vmumm/y2020/i4/p51
|
Statistics & downloads: |
Abstract page: | 130 | Full-text PDF : | 11 | References: | 17 | First page: | 10 |
|