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

А.С. Балюк

Иркутский государственный университет, г. Иркутск, 664003, Россия

Полный текст PDF
DOI: 10.26907/2541-7746.2020.3.285-299

Для цитирования: Балюк А.С. Сложность псевдокронекеровых и свободно кроне\ керовых форм функций над конечными полями // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 3. – С. 285–299. – doi: 10.26907/2541-7746.2020.3.285-299.

For citation: Baliuk A.S. The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 285–299. doi: 10.26907/2541-7746.2020.3.285-299. (In Russian)

Аннотация

Предложен подход, позволяющий частично обобщить иерархию Грина – Сасао полиномиальных форм булевых функций на случай произвольного конечного поля.

Для сложности псевдокронекеровых и свободно кронекеровых форм n-местных функций над произвольным конечным полем Fq найдено точное значение функции Шеннона, которое оказывается равным qn−1. Работа обобщает ранее известный результат для булевых функций.

Ключевые слова: конечное поле, сложность вычислений, свободно кронекеровы формы, псевдокронекеровы формы

Благодарности. Работа выполнена при поддержке РФФИ (проект № 19-01-00200).

Литература

  1. Green D.H. Families of Reed-Muller canonical forms // Int. J. Electron. – 1991. – V. 70, No 2. – P. 259–280. – doi: 10.1080/00207219108921277.
  2. Sasao T. Representations of logic functions using EXOR operators // Representations of Discrete Functions. – Boston: Kluwer Acad. Publ., 1996. – P. 29–54. – doi: 10.1007/978-1-4613-1385-4_2.
  3. Ho P., Perkowski M. Free Kronecker decision diagrams and their application to Atmel 6000 series FPGA mapping // Proc. Conf. on European Design Automation. – Grenoble, France, 1994. – P. 8–13. – doi: 10.1145/198174.198180.
  4. Al-Rabadi A.N. An extended Green-Sasao hierarchy of canonical ternary Galois forms and Universal Logic Modules // Facta Univ., Ser.: Electron. Energ. – 2017. – V. 30, No 1, P. 49–66. – doi: 10.1080/00207219108921277.
  5. Избранные вопросы теории булевых функций / Под ред. С.Ф. Винокурова, Н.А. Перязева. – М.: Физматлит, 2001. – 192 p.
  6. Балюк А.С., Винокуров С.Ф. Функция Шеннона для некоторых классов операторных полиномиальных форм // Оптимизация, управление, интеллект. – 2000. – Т. 5, № 1. – С. 111–121.
  7. Балюк А.С., Зинченко А.С. Нижние оценки сложности поляризованных полиномов над конечными полями // Сиб. матем. журн. – 2019. – V. 60, No 1. – P. 3–13. – doi: 10.1134/S0037446619010014.
  8. Mullen G.L., Panarino D. Handbook of Finite Fields. – N. Y.: Chapman and Hall/CRC, 2013. – 1068 p. – doi: 10.1201/b15006.
  9. Baluck A.S., Vinokurov S.F. Classes of operator forms // 5th Int. Workshop on Boolean Problems. – Freiberg, Germany, 2002. – P. 76–83.
  10. Перязев Н.А. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика. – 1995. – Т. 34, № 3. – С. 323–326.
  11. Селезнева С.Н. О сложности представления функций многозначных логик поляризованными полиномами // Дискрет. матем. – 2002. – Т. 14, № 2. – С. 48–53.
  12. Алексеев В.Б., Вороненко А.А., Селезнева С.Н. О сложности реализации функций k-значной логики поляризованными полиномами // Труды V Междунар. конференции «Дискретные модели в теории управляющих систем». – Ратмино, 2003. – С. 8–9.
  13. Балюк А.С., Янушковский Г.В. Верхние оценки сложности функций над конечными полями в некоторых классах кронекеровых форм // Изв. Иркут. гос. ун-та. Сер. «Математика». – 2015. – № 14. – С. 3–17.
  14. Казимиров А.С., Реймеров С.Ю. Верхние оценки сложности функций над непростыми конечными полями в классе поляризованных полиномов // Изв. Иркут. гос. ун-та. Сер.«Математика». – 2016. – № 17. – С. 37–45.
  15. Маркелов Н.К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем и кибернетика. – 2012. – № 3. – С. 40–45.
  16. Селезнева С.Н. О сложности k-значных функций в одном классе полиномов // Проблемы теоретической кибернетики: Материалы XVI Междунар. конф. – Н. Новгород, 2011. – С. 430–434.
  17. Балюк А.С. О верхней оценке сложности задания квазиполиномами функций над конечными полями //Изв. Иркут. гос. ун-та. Сер.«Математика». – 2014. – № 10. – С. 3–12.
  18. Балюк А.С. Методы получения оценок сложности кронекеровых форм функций над конечными полями // Труды X Междунар. конф. «Дискретные модели в теории управляющих систем». – Москва и Подмосковье, 2018. – С. 46–49.
  19. Цирлер Н. Линейные возвратные последовательности // Кибернетический сб. – М.: Изд-во иностр. лит., 1963. – Вып. 6. – С. 55–79.

Поступила в редакцию 18.08.2020

 

Балюк Александр Сергеевич, кандидат физико-математических наук, доцент Института математики и информационных технологий

Иркутский государственный университет

ул. Карла Маркса, д. 1, г. Иркутск, 664003, Россия

E-mail: sacha@hotmail.ru

 

Контент доступен под лицензией Creative Commons Attribution 4.0 License.