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

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

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



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Сиб. электрон. матем. изв., 2019, том 16, страницы 523–541 (Mi semr1076)  

Дискретная математика и математическая кибернетика

Сложность представлений булевых функций в классах расширенных двупорожденных операторных форм

А. С. Францева

Irkutsk State University, 1, Karl Marx str., Irkutsk, 664003, Russia

Аннотация: In this paper, we study the problem of receiving the complexity's value of Boolean functions' representations in some classes of polynomial normal forms or exclusive-or sum-of-products expressions (ESOPs). These classes are extensions of known classes of polarized Zhegalkin polynomials or Reed-Muller forms and the Kronecker forms' class. An operator approach for the ESOPs classes' description is used in the work. A Boolean function is represented as a sum of operator images with respect to some basis function. If we consider the product's function as the basic function, then the classes of operator forms are becoming the ESOPs. In this paper, we received estimates of the complexity's value in various classes of extended pair-generated operator forms. The lower bound of the complexity's value to the class of all extended pair-generated operator forms (A. Baliuk and S. Vinokourov, 2001) was improved.

Ключевые слова: Boolean functions, polynomial normal forms, exclusive-or sum-of-products expressions, extended pair-generated operator forms.

DOI: https://doi.org/10.33048/semi.2019.16.034

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

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

Тип публикации: Статья
УДК: 519.714.4
MSC: 06E30
Поступила 26 июля 2019 г., опубликована 19 апреля 2019 г.

Образец цитирования: А. С. Францева, “Сложность представлений булевых функций в классах расширенных двупорожденных операторных форм”, Сиб. электрон. матем. изв., 16 (2019), 523–541

Цитирование в формате AMSBIB
\RBibitem{Fra19}
\by А.~С.~Францева
\paper Сложность представлений булевых функций в классах расширенных двупорожденных операторных форм
\jour Сиб. электрон. матем. изв.
\yr 2019
\vol 16
\pages 523--541
\mathnet{http://mi.mathnet.ru/semr1076}
\crossref{https://doi.org/10.33048/semi.2019.16.034}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr1076
  • http://mi.mathnet.ru/rus/semr/v16/p523

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:2
    Литература:1

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019