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

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

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



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






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


Дискретная математика, 2022, том 34, выпуск 3, страницы 90–113
DOI: https://doi.org/10.4213/dm1503
(Mi dm1503)
 

О сложности реализации булевых функций в некоторых классах гиперконтактных схем

Ю. Г. Таразевич

Белорусский государственный университет
Список литературы:
Аннотация: В классах $\operatorname{\text{РМ}}_F^{(n)}$ расширенных матриц над кольцами полиномов с идемпотентными переменными определены подклассы (гиперконтактных схем): $\operatorname{\text{ГС}}_F^{(n)}$ (над произвольным полем $F$) и $\operatorname{\text{ГС}}_Z^{(n)}$ (над кольцом целых чисел), — алгебраически расширяющие класс матриц инциденций контактных схем ($\operatorname{\text{КС}}^{(n)}$) и реализующие произвольные булевы функции $n$ переменных со сложностью менее $3\sqrt{2}\cdot2^{n/2}$ контактов. Такой же порядок нижней оценки получен для соответствующей функции Шеннона в классе $\operatorname{\text{ГС}}_{F_q}^{(n)}$ над произвольным конечным полем $F_q$. Для матриц класса $\operatorname{\text{ГС}}_Z^{(n)}$ найдена физическая интерпретация в виде матриц инциденций-зацеплений контактно-трансформаторных схем.
Ключевые слова: полином с идемпотентными переменными, гиперконтактная схема, контактный гиперграф, контактный матроид, матрица инциденций-зацеплений, контактно-трансформаторная схема.
Статья поступила: 09.02.2018
Переработанный вариант поступил: 24.12.2021
Англоязычная версия:
Discrete Mathematics and Applications, 2024, Volume 34, Issue 1, Pages 33–50
DOI: https://doi.org/10.1515/dma-2024-0004
Тип публикации: Статья
УДК: 519.714.4
Образец цитирования: Ю. Г. Таразевич, “О сложности реализации булевых функций в некоторых классах гиперконтактных схем”, Дискрет. матем., 34:3 (2022), 90–113; Discrete Math. Appl., 34:1 (2024), 33–50
Цитирование в формате AMSBIB
\RBibitem{Tar22}
\by Ю.~Г.~Таразевич
\paper О сложности реализации булевых функций в~некоторых классах гиперконтактных схем
\jour Дискрет. матем.
\yr 2022
\vol 34
\issue 3
\pages 90--113
\mathnet{http://mi.mathnet.ru/dm1503}
\crossref{https://doi.org/10.4213/dm1503}
\transl
\jour Discrete Math. Appl.
\yr 2024
\vol 34
\issue 1
\pages 33--50
\crossref{https://doi.org/10.1515/dma-2024-0004}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/dm1503
  • https://doi.org/10.4213/dm1503
  • https://www.mathnet.ru/rus/dm/v34/i3/p90
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Статистика просмотров:
    Страница аннотации:302
    PDF полного текста:51
    Список литературы:58
    Первая страница:24
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024