Geodesic
On bijunctive predicates over a~finite set
Diskretnaya Matematika, Tome 29 (2017) no. 4, pp. 130-142.

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

The paper is concerned with representations of predicates over a finite set in the form of generalized conjunctive normal forms (GCNF). Properties of predicates GCNF are found which are preserved by some majority function. Such predicates are called generalized bijunctive predicates. These properties are used to construct new faster polynomial algorithms for the generalized satisfiability problem in the case when some majority function preserves all the original predicates.
Keywords: predicate over a finite set, function over a finite set, majority function, bijunctive predicate, conjunctive normal form, generalized satisfiability problem (constraint satisfaction problems), polynomial problem. 
@article{DM_2017_29_4_a8,
     author = {S. N. Selezneva},
     title = {On bijunctive predicates over a~finite set},
     journal = {Diskretnaya Matematika},
     pages = {130--142},
     publisher = {mathdoc},
     volume = {29},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2017_29_4_a8/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - On bijunctive predicates over a~finite set
JO  - Diskretnaya Matematika
PY  - 2017
SP  - 130
EP  - 142
VL  - 29
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2017_29_4_a8/
LA  - ru
ID  - DM_2017_29_4_a8
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T On bijunctive predicates over a~finite set
%J Diskretnaya Matematika
%D 2017
%P 130-142
%V 29
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2017_29_4_a8/
%G ru
%F DM_2017_29_4_a8
S. N. Selezneva. On bijunctive predicates over a~finite set. Diskretnaya Matematika, Tome 29 (2017) no. 4, pp. 130-142. http://geodesic.mathdoc.fr/item/DM_2017_29_4_a8/

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

[2] 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

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

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

[5] 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

[6] Dubrova E., Jiang Yu., Brayton R., “Minimization of multiple-valued functions in Post algebra”, Proc. Int. Workshop on Logic Synthesis, 2001, 132–137

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

[8] 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 | MR | Zbl

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

[10] Alekseev V. B., Vvedenie v teoriyu slozhnosti algoritmov, Izd. otdel f-ta VMiK MGU, M., 2002, 82 pp.