|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
On properties of multiaffine predicates on a finite setстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 сентября 2023 г.
- Автор: Selezneva S.N.
- Журнал: Discrete Mathematics and Applications
- Том: 33
- Номер: 4
- Год издания: 2023
- Издательство: de Gruyter
- Местоположение издательства: Germany
- Первая страница: 259
- Последняя страница: 267
- DOI: 10.1515/dma-2023-0023
- Аннотация: We consider predicates on a finite set that are invariant with respect to an affine operation f_G, where G is some Abelian group. Such predicates are said to be multiaffine for the group G. Special attention is paid to predicates that are affine for the group G_q of addition modulo q=p^s, where p is a prime number and s >= 1. We establish the predicate multiaffinity criterion for the group G_q. Then we introduce disjunctive normal forms (DNF) for predicates on a finite set and obtain properties of DNFs of predicates that are multiaffine for the group G_q. Finally we show how these properties can be used to design a polynomial algorithm that decides satisfiability of a system of predicates which are multiaffine for the group G_q, if predicates are specified by DNF.
- Добавил в систему: Селезнева Светлана Николаевна