On properties of multiaffine predicates on a finite setстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 сентября 2023 г.
Аннотация: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.