Geodesic
On m-junctive predicates on a finite set
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 3, pp. 46-59.

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

We consider predicates on finite sets. The predicates invariant under some (m+1)-ary near-unanimity function are called m-junctive. We propose to represent the predicates on a finite set in generalized conjunctive normal forms (GCNFs). The properties for GCNFs of m-junctive predicates are obtained. We prove that each m-junctive predicate can be represented by a strongly consistent GCNF in which every conjunct contains at most m variables. This representation of an m-junctive predicate is called reduced. Some fast algorithm is proposed for finding a reduced representation for an m-junctive predicate. It is shown how the obtained properties of GCNFs of m-junctive predicates can be applied for constructing a fast algorithm for the generalized S-satisfiability problem in the case that S contains only the predicates invariant under a common near unanimity function. Bibliogr. 15.
Mots-clés : predicate on a finite set, function on a finite set, near-unanimity function, bijunctive predicate, m-junctive predicate, conjunctive normal form, generalized satisfiability problem. 
@article{DA_2019_26_3_a2,
     author = {S. N. Selezneva},
     title = {On $m$-junctive predicates on a finite set},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {46--59},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2019},
     language = {ru},
     url = {https://geodesic-test.mathdoc.fr/item/DA_2019_26_3_a2/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - On $m$-junctive predicates on a finite set
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 46
EP  - 59
VL  - 26
IS  - 3
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DA_2019_26_3_a2/
LA  - ru
ID  - DA_2019_26_3_a2
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T On $m$-junctive predicates on a finite set
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 46-59
%V 26
%N 3
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DA_2019_26_3_a2/
%G ru
%F DA_2019_26_3_a2
S. N. Selezneva. On $m$-junctive predicates on a finite set. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 3, pp. 46-59. https://geodesic-test.mathdoc.fr/item/DA_2019_26_3_a2/

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

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

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

[4] Zhuk D., “A proof of CSP dichotomy conjecture”, Proc. IEEE 58th Annu. Symp. Foundations of Computer Science (Berkeley, CA), 2017, 331–342 | MR

[5] Bulatov A. A., “A dichotomy theorem for nonuniform CSPs”, Proc. IEEE 58th Annu. Symp. Foundations of Computer Science (Berkeley, CA), 2017, 319–330 | 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., Cohen D., Cooper M., “Constraints, consistency and closure”, Artif. Intell., 101:1–2 (1998), 251–265 | DOI | MR | Zbl

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

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

[11] S. N. Selezneva, “On bijunctive predicates over a finite set”, Discret. Math. Appl., 29 (2019), 49–58 | DOI | DOI | MR | MR | Zbl

[12] S. N. Selezneva, “On weak positive predicates over a finite set”, Diskretn. Mat., 30:3 (2018), 127–140 (Russian) | DOI | MR

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

[14] Cooper M. C., “An optimal $k$-consistency algorithm”, Artif. Intell., 41 (1989), 89–95 | DOI | MR | Zbl

[15] Lau D., Function algebras on finite sets, Springer, Berlin, 2006 | MR | Zbl