RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискрет. матем., 2014, том 26, выпуск 4, страницы 100–109 (Mi dm1308)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Мультипликативная сложность некоторых функций алгебры логики

С. Н. Селезнева

Московский государственный университет им. М. В. Ломоносова

Аннотация: Мультипликативной (или конъюнктивной) сложностью функции алгебры логики $f(x_1, …, x_n)$ (соответственно, системы функций алгебры логики $F = \{f_1, …, f_m\}$) называется минимальное число элементов конъюнкции в схемах из функциональных элементов в базисе $\{x& y, x \oplus y, 1\}$, каждая из которых реализует функцию $f$ (соответственно, все функции из системы $F$). Мультипликативную сложность функции $f$ (системы функций $F$) будем обозначать через $\mu(f)$ (через $\mu(F)$). В работе доказано, что $\mu(f) = n-1$, если функция $f(x_1, …, x_n)$ представима в виде $x_1x_2…x_n \oplus q(x_1, …, x_n)$, где $q$ – функция степени два ($n \ge 3$). В работе также доказано, что $\mu(f) \le n-1$, если функция $f(x_1, …, x_n)$ представима в виде суммы по модулю $2$ двух мультиаффинных функций. Кроме того, в работе показано, что $\mu(F) = n-1$, если $F = \{x_1x_2…x_n, f(x_1, …, x_n)\}$, где $f$ – или функция степени два, или мультиаффинная функция. Работа поддержана РФФИ, гранты 13-01-00684-а и 13-01-00958-а.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 13-01-00684-а
13-01-00958-а
Работа поддержана РФФИ, гранты 13-01-00684-а и 13-01-00958-а.


DOI: https://doi.org/10.4213/dm1308

Полный текст: PDF файл (438 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Discrete Mathematics and Applications, 2015, 25:2, 101–108

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.713
Статья поступила: 23.05.2014

Образец цитирования: С. Н. Селезнева, “Мультипликативная сложность некоторых функций алгебры логики”, Дискрет. матем., 26:4 (2014), 100–109; Discrete Math. Appl., 25:2 (2015), 101–108

Цитирование в формате AMSBIB
\RBibitem{Sel14}
\by С.~Н.~Селезнева
\paper Мультипликативная сложность некоторых функций алгебры логики
\jour Дискрет. матем.
\yr 2014
\vol 26
\issue 4
\pages 100--109
\mathnet{http://mi.mathnet.ru/dm1308}
\crossref{https://doi.org/10.4213/dm1308}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3467229}
\elib{https://elibrary.ru/item.asp?id=22834165}
\transl
\jour Discrete Math. Appl.
\yr 2015
\vol 25
\issue 2
\pages 101--108
\crossref{https://doi.org/10.1515/dma-2015-0010}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000366853400004}
\elib{https://elibrary.ru/item.asp?id=24023422}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84927937365}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1308
  • https://doi.org/10.4213/dm1308
  • http://mi.mathnet.ru/rus/dm/v26/i4/p100

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. А. Городилова, “От криптоанализа шифра к криптографическому свойству булевой функции”, ПДМ, 2016, № 3(33), 16–44  mathnet  crossref
    2. Selezneva S.N., “On the Multiplicative Complexity of Boolean Functions”, Fundam. Inform., 145:3 (2016), 399–404  crossref  mathscinet  zmath  isi  elib  scopus
  • Дискретная математика
    Просмотров:
    Эта страница:260
    Полный текст:66
    Литература:32
    Первая стр.:36
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020