|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
О свойствах мультиаффинных предикатов на конечном множествестатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Автор: Селезнева С.Н.
- Журнал: Дискретная математика
- Том: 33
- Номер: 4
- Год издания: 2021
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 141
- Последняя страница: 152
- DOI: 10.4213/dm1654
- Аннотация: Рассматриваются предикаты на конечном множестве, инвариантные относительно аффинной операции f_G, где G - некоторая коммутативная группа. Такие предикаты названы мультиаффинными по группе G. Основное внимание уделено предикатам, мультиаффинным по группе G_q сложения по модулю q=p^s, где p — простое число, s>=1. Установлен критерий мультиаффинности предикатов по группе G_q. Введены дизъюнктивные нормальные формы (ДНФ) для предикатов на конечном множестве и найдены свойства ДНФ предикатов, мультиаффинных по группе G_q. Показано, каким образом на основе этих свойств можно построить полиномиальный алгоритм проверки выполнимости системы предикатов, мультиаффинных по группе G_q, если предикаты заданы в виде ДНФ.
- Добавил в систему: Селезнева Светлана Николаевна