Отправить статью по E-mail Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts
- Авторы: Selezneva S.N.1
-
Учреждения:
- Department of Computational Mathematics and Cybernetics
- Выпуск: Том 40, № 3 (2016)
- Страницы: 123-127
- Раздел: Article
- URL: https://journals.rcsi.science/0278-6419/article/view/176142
- DOI: https://doi.org/10.3103/S0278641916030043
- ID: 176142
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function LESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that LESPP(n) = Ɵ (2n/n2). The quantity LESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.
Об авторах
S. Selezneva
Department of Computational Mathematics and Cybernetics
Автор, ответственный за переписку.
Email: selezn@cs.msu.su
Россия, Moscow, 119991
Дополнительные файлы
