Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:3, 528-535
Volume 26, No 3, 2019, P. 46-59
UDC 519.7
S. N. Selezneva
On $m$-junctive predicates on a finite set
Abstract:
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.
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
1. Lomonosov Moscow State University,
1 Leninskie Gory, 119991 Moscow, Russia
e-mail: selezn@cs.msu.ru
Received February 5, 2019
Revised March 21, 2019
Accepted March 25, 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).
