On properties of multiaffine predicates on a finite set
Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 141-152
Voir la notice de l'article provenant de la source Math-Net.Ru
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 a group $G_q$ of addition modulo $q = p^s$, where $p$ is a prime number and $s \geqslant 1$. We establish the predicate multiaffinity criterion for a 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 a 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 a group $G_q$, if predicates are specified by DNF.
Keywords:
predicate on a finite set, function on a finite set, affine operation, multiaffinity, disjunctive normal form, algorithm, complexity, polynomial algorithm.
@article{DM_2021_33_4_a11,
author = {S. N. Selezneva},
title = {On properties of multiaffine predicates on a finite set},
journal = {Diskretnaya Matematika},
pages = {141--152},
publisher = {mathdoc},
volume = {33},
number = {4},
year = {2021},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DM_2021_33_4_a11/}
}
S. N. Selezneva. On properties of multiaffine predicates on a finite set. Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 141-152. http://geodesic.mathdoc.fr/item/DM_2021_33_4_a11/