Том 27, номер 1, 2020 г., Стр. 110–126

УДК 519.97
Парватов Н. Г.
Нахождение множеств переменных частичной булевой функции, достаточных для её реализации в классах, задаваемых предикатами

Аннотация:
Для заданного класса $K$ частичных булевых функций и произвольной частичной булевой функции $f$ от $n$ переменных множество $U$ её переменных называется достаточным для реализации в классе $K$, если в этом классе найдётся функция, доопределяющая $f$ и зависящая от переменных из множества $U$. В статье рассматривается задача нахождения всех множеств, достаточных для реализации функции $f$ в классе $K$. Для ряда классов, задаваемых отношениями, предлагаются алгоритмы, решающие указанную задачу со сложностью $O(2^{n} n ^ {2})$ битовых операций. В том числе построены алгоритмы указанной сложности для классов $P^*_2$ всех частичных булевых функций и $M^*_2$ всех частичных монотонных функций. Предлагаемые алгоритмы основаны на использовании преобразований Уолша — Адамара и Мёбиуса.
Библиогр. 21.

Ключевые слова: частичная булева функция, достаточное множество переменных, преобразование Уолша — Адамара, преобразование Мёбиуса.

DOI: 10.33048/daio.2020.27.664

Парватов Николай Георгиевич¹
1. Томский государственный университет,
пр. Ленина, 36, 634050, Томск, Россия
е-mail: ngparvatov@yandex.ru

Статья поступила 20 июня 2019 г.
После доработки — 5 ноября 2019 г.
Принята к публикации 27 ноября 2019 г.

Литература

[1] Golubeva O. I. Construction of permissible functions and their application for fault tolerance // Proc. 2019 Int. Sib. Conf. Control Communications (Tomsk, Russia, Apr. 18–20, 2019). Tomsk: TUSUR, 2019. P. 1–5.

[2] Вороненко А. А. О методе разложения для распознавания принадлежности инвариантным классам // Дискрет. математика. 2002. T. 14, № 4. C. 110–116.

[3] Selezneva S. N. Constructing polynomials for functions over residue rings modulo a composite number in linear time // Computer science — Theory and applications. Heidelberg: Springer, 2012. P. 302–313. (Lect. Notes Comput. Sci.; Vol. 7353).

[4] Алексеев В. Б., Емельянов Н. Р. Метод построения быстрых алгоритмов в $k$-значной логике // Мат. заметки. 1985. Т. 38, вып. 1. С. 148–156.

[5] Алексеев В. Б. Ступенчатые билинейные алгоритмы и распознавание полноты в $k$-значных логиках // Изв. вузов. Математика. 1988. № 7. C. 19–27.

[6] Алексеев В. Б. Логические полукольца и их использование для построения быстрых алгоритмов // Вестн. Моск. ун-та. Сер. 1. 1997. № 1. С. 22–29.

[7] Парватов Н. Г. Порождение достаточных множеств аргументов частичной булевой функции // Вестн. Томск. гос. ун-та. Прил. 2007. № 23. С. 44–48.

[8] Сачков В. Н. Комбинаторные методы дискретной математики. М.: Наука, 1977.

[9] Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

[10] Rushforth С. К. Fast Fourier–Hadamard decoding of orthogonal codes // Inform. Control. 1969. Vol. 15, No. 1. P. 33–37.

[11] Малютин А. А. Быстрое корреляционное декодирование некоторых подмножеств слов кода Рида — Маллера первого порядка // Дискрет. математика. 1990. Т. 2, вып. 2, C. 155–158.

[12] Карякин Ю. Д. Быстрое корреляционное декодирование кодов Рида — Маллера // Пробл. передачи информации. 1987. Т. 23, вып. 2, С. 40–49.

[13] Токарева Н. Н. Обобщения бент-функций. Обзор работ // Дискрет. анализ и исслед. операций. 2010. Т. 17, № 1. C. 33–62.

[14] Weisner L. Abstract theory of inversion of finite series // Trans. Amer. Math. Soc. 1935. Vol. 38. P. 474–484.

[15] Hall P. The Eulerian functions of a group // Q. J. Math. 1936. Vol. 7. P. 134–151.

[16] Rota G.-C. On the foundations of combinatorial theory: I. Theory of Möbius functions // Z. Wahrscheinlichkeitstheor. Verw. Geb. 1964. Vol. 2. P. 340–368.

[17] Stanley R. P. Enumerative combinatorics. Vol. 1. New York: Camb. Univ. Press, 1997. (Camb. Stud. Adv. Math.; Vol. 49).

[18] Парватов Н. Г. О распознавании свойств дискретных функций схемами из функциональных элементов // Вестн. Томск. гос. ун-та. Прил. 2005. № 14. С. 233–236.

[19] Schönhage A., Strassen V. Schnelle Multiplikation groβer Zahlen // Computing. 1971. Vol. 7. P. 281–292. [German].

[20] Fürer M. Faster integer multiplication // Proc. 39th Annual ACM Symp. Theory Comput. (San Diego, CA, USA, June 11–13, 2007). New York: ACM, 2007. P. 57–66.

[21] De A., Kurur P. P., Saha C., Saptharishi R. Fast integer multiplication using modular arithmetic // Proc. 40th Annual ACM Symp. Theory Comput. (Victoria, Canada, May 17–20, 2008). New York: ACM, 2008. P. 499–506.