EN|RU
English version: Journal of Applied and Industrial Mathematics, 2019, 13:3, 528-535 |
![]() |
Volume 26, No 3, 2019, P. 46-59 UDC 519.7
Keywords: predicate on a finite set, function on a finite set, near-unanimity function, bijunctive predicate, $m$-junctive predicate, conjunctive normal form, generalized satisfiability problem. DOI: 10.33048/daio.2019.26.647 Svetlana N. Selezneva 1 Received February 5, 2019 References[1] P. Jeavons, D. Coher, and M. Gyssens, Closure properties of constraints, J. ACM 44, 527–548 (1997).[2] A. Bulatov, P. Jeavons, and A. Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput. 34, 720–742 (2005). [3] D. Zhuk, An algorithm for constraint satisfaction problem, in Proc. IEEE 47th Int. Symp. Multiple-Valued Logic, 2017, pp. 1–6. [4] D. Zhuk, A proof of CSP dichotomy conjecture, in Proc. IEEE 58th Annual Symp. Foundations Computer Science, Berkeley, CA, 2017, pp. 331–342. [5] A. A. Bulatov, A dichotomy theorem for nonuniform CSPs, in Proc. IEEE 58th Annual Symp. Foundations Computer Science, Berkeley, CA, 2017, pp. 319–330. [6] T. Schaefer, Complexity of satisfiability problems, in Proc. 10th ACM Symp. Theory Computing, 1978, [7] A. A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a 3-Element Set, J. ACM 53, 66–120 (2006). [8] P. Jeavons, D. Cohen, and M. Cooper, Constraints, consistency, and closure, Artif. Intell. 101, 251–265 (1998). [9] P. J. Jeavons and M. C. Cooper, Tractable constraints on ordered domains, Artif. Intell. 79, 327–339 (1995). [10] A. A. Bulatov, The property of being polynomial for Mal'tsev constraint satisfaction problems, Algebra Logika 45, 655–686 (2006) [Russian] [Algebra Logic 45, 371–388 (2006)]. [11] S. N. Selezneva, On bijunctive predicates over a finite set, Diskretn. Mat. 29 (4) 130–142 (2017) [Russian] [Discret. Math. Appl. 29, 49–58 (2019)]. [12] S. N. Selezneva, On weak positive predicates over a finite set, Diskretn. Mat. 30 (3), 127–140 (2018) [Russian]. [13] R. Dechter, From local to global consistency, Artif. Intell. 55, 87–107 (1992). [14] M. C. Cooper, An optimal k-consistency algorithm, Artif. Intell. 41, 89–95 (1989). [15] D. Lau, Function Algebras on Finite Sets (Springer, Berlin, 2006). |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|