Geodesic
On weak positive predicates over a finite set
Diskretnaya Matematika, Tome 30 (2018) no. 3, pp. 127-140.

Voir la notice de l'article provenant de la source Math-Net.Ru

Predicates that are preserved by a semi-lattice function are considered. These predicates are called weak positive. A representation of these predicates are proposed in the form of generalized conjunctive normal forms (GCNFs). Properties of GCNFs of these predicates are obtained. Based on the properties obtained, more efficient polynomial-time algorithms are proposed for solving the generalized satisfiability problem in the case when all initial predicates are preserved by a certain semi-lattice function.
Keywords: predicate over a finite set, function over a finite set, semi-lattice function, weak positive predicate, conjunctive normal form, generalized satisfiability problem (constraints satisfaction problem), polynomial-time problem. 
@article{DM_2018_30_3_a10,
     author = {S. N. Selezneva},
     title = {On weak positive predicates over a finite set},
     journal = {Diskretnaya Matematika},
     pages = {127--140},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2018_30_3_a10/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - On weak positive predicates over a finite set
JO  - Diskretnaya Matematika
PY  - 2018
SP  - 127
EP  - 140
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2018_30_3_a10/
LA  - ru
ID  - DM_2018_30_3_a10
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T On weak positive predicates over a finite set
%J Diskretnaya Matematika
%D 2018
%P 127-140
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2018_30_3_a10/
%G ru
%F DM_2018_30_3_a10
S. N. Selezneva. On weak positive predicates over a finite set. Diskretnaya Matematika, Tome 30 (2018) no. 3, pp. 127-140. http://geodesic.mathdoc.fr/item/DM_2018_30_3_a10/

[1] Jeavons P., Cohen D., Cooper M., “Constraints, consistency and closure”, Artificial Intelligence, 101:1-2 (1998), 251–265 | DOI | MR | Zbl

[2] Jeavons P., Coher D., Gyssens M., “Closure properties of constraints”, J. ACM, 44 (1997), 527–548 | DOI | MR | Zbl

[3] Bulatov A., Jeavons P., Krokhin A., “Classifying the complexity of constraints using finite algebras”, SIAM J. Comput., 34:3 (2005), 720–742 | DOI | MR | Zbl

[4] Maroti M., Mckenzie R., “Existence theorems for weakly symmetric operations”, Algebra Universalis, 59:3-4 (2008), 463–489 | DOI | MR | Zbl

[5] Zhuk D., “An algorithm for constraint satisfaction problem”, Proc. IEEE 47th Int. Symp. Multiple-Valued Logic, 2017, 1–6 | MR

[6] Schaefer T., “Complexity of satisfiability problems”, Proc. 10th ACM Symp. Theory of Computing, 1978, 216–226 | MR | Zbl

[7] Bulatov A. A., “A dichotomy theorem for constraint satisfaction problems on a 3-element set”, J. ACM, 53:1 (2006), 66–120 | DOI | MR | Zbl

[8] Jeavons P.J., Cooper M.C., “Tractable constraints on ordered domains”, Artificial Intelligence, 79 (1995), 327–339 | DOI | MR | Zbl

[9] Bulatov A.A., “The property of being polynomial for Mal’tsev constraint satisfaction problems”, Algebra and Logic, 45:6 (2006), 371–388 | DOI | MR | Zbl

[10] Selezneva S.N., “O biyunktivnykh predikatakh nad konechnym mnozhestvom”, Diskretnaya matematika, 29:4 (2017), 130–142 | DOI | MR

[11] Yablonskii S.V., “Funktsionalnye postroeniya v $k$-znachnoi logike”, Sbornik statei po matematicheskoi logike i ee prilozheniyam k nekotorym voprosam kibernetiki, Tr. MIAN SSSR, 51, Izd-vo AN SSSR, M., 1958, 5–142

[12] Dechter R., “From local to global consistency”, Artificial Intelligence, 55 (1992), 87–107 | DOI | MR | Zbl