Affine systems of equations and counting infinitary logic. (English) Zbl 1168.68040
Summary: We study the definability of Constraint Satisfaction Problems (CSPs) in various fixed-point and infinitary logics. We show that testing the solvability of systems of equations over a finite abelian group, a tractable CSP that was previously known not to be definable in Datalog, is not definable in the infinitary logic with finitely many variables and counting. This implies that it is not definable in least fixed-point logic or its extension with counting. We relate definability of CSPs to their classification obtained from tame congruence theory of the varieties generated by the algebra of polymorphisms of the template structure. In particular, we show that if this variety admits either the unary or affine type, the corresponding CSP is not definable in the infinitary logic with counting.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 03C13 | Model theory of finite structures |
| 03C75 | Other infinitary logic |
| 08A70 | Applications of universal algebra in computer science |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
constraint satisfaction problem; finite model theory; universal algebra; infinitary logic with counting; tame congruence theory; bijective game; systems of linear equations; inexpressibility; quantifier-free reductionsReferences:
| [1] | Blass, A.; Gurevich, Y.; Shelah, S., On polynomial time computation over unordered structures, Journal of Symbolic Logic, 67, 3, 1093-1125 (2002) · Zbl 1020.03038 |
| [2] | Bodnarchuk, V. G.; Kaluzhnin, L. A.; Kotov, V. N.; Romov, B. A., Galois theory for post algebras. i, Kibernetika, 3, 1-10 (1969), (in Russian) · Zbl 0212.31802 |
| [3] | Bulatov, A. A.; Dalmau, V., A simple algorithm for Mal’tsev constraints, SIAM Journal on Computing, 36, 1, 16-27 (2006) · Zbl 1112.08002 |
| [4] | Bulatov, A. A.; Jeavons, P.; Krokhin, A., Classifying the complexity of constraints using finite algebras, SIAM Journal on Computing, 34, 720-742 (2005) · Zbl 1071.08002 |
| [5] | A.A. Bulatov, Mal’tsev constraints are tractable, Technical Report PRG-RR-02-05, Computing Laboratory, University of Oxford, Oxford, UK, 2002; A.A. Bulatov, Mal’tsev constraints are tractable, Technical Report PRG-RR-02-05, Computing Laboratory, University of Oxford, Oxford, UK, 2002 |
| [6] | A.A. Bulatov, P.G. Jeavons, Algebraic structures in combinatorial problems, Technical Report MATH-AL-4-2001, Technische universität Dresden, Dresden, Germany, 2001; A.A. Bulatov, P.G. Jeavons, Algebraic structures in combinatorial problems, Technical Report MATH-AL-4-2001, Technische universität Dresden, Dresden, Germany, 2001 |
| [7] | Buntrock, G.; Damm, C.; Hertrampf, U.; Meinel, C., Structure and importance of logspace-MOD class, Mathematical Systems Theory, 25, 223-237 (1992) · Zbl 0749.68033 |
| [8] | Burris, S.; Sankappanavar, H. P., (A Course in Universal Algebra. A Course in Universal Algebra, Graduate Texts in Mathematics, vol. 78 (1981), Springer-Verlag: Springer-Verlag New York, Berlin) · Zbl 0478.08001 |
| [9] | Dalmau, V., Linear datalog and bounded path duality of relational structures, Logical Methods in Computer Science, 1, 1 (2005) · Zbl 1125.68408 |
| [10] | Dalmau, V.; Kolaitis, Ph. G.; Vardi, M. Y., Constraint satisfaction, bounded treewidth, and finite variable logics, (Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, CP’02. Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, CP’02, Lecture Notes in Computer Science (2002), Springer-Verlag), 311-326 · Zbl 1535.68111 |
| [11] | Dawar, A., A restricted second order logic for finite structures, Information and Computation, 143, 154-174 (1998) · Zbl 0909.68078 |
| [12] | Diestel, R., Graph Theory (1997), Springer · Zbl 0873.05001 |
| [13] | Ebbinghaus, H.-D.; Flum, J., Finite Model Theory (1999), Springer · Zbl 0932.03032 |
| [14] | Feder, T.; Vardi, M. Y., Computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory, SIAM Journal of Computing, 28, 57-104 (1998) · Zbl 0914.68075 |
| [15] | Geiger, D., Closed systems of function and predicates, Pacific Journal of Mathematics, 95-100 (1968) · Zbl 0186.02502 |
| [16] | Hella, L., Logical hierarchies in PTIME, Information and Computation, 129, 1-19 (1996) · Zbl 0864.68095 |
| [17] | Herrman, C., Affine algebras in congruence-modular varieties, Acta Scientiarum Mathematicarum (Szeged), 41, 119-125 (1971) · Zbl 0408.08003 |
| [18] | Hobby, D.; Mckenzie, R. N., (The Structure of Finite Algebras. The Structure of Finite Algebras, Contemporary Mathematics, vol. 76 (1988), American Mathematical Society: American Mathematical Society Providence, R.I) · Zbl 0721.08001 |
| [19] | Immerman, N., Descriptive Complexity (1999), Springer · Zbl 0918.68031 |
| [20] | Jeavons, P. G.; Cohen, D. A.; Gyssens, M., Closure properties of constraints, Journal of the ACM, 44, 527-548 (1997) · Zbl 0890.68064 |
| [21] | Jeavons, P. G.; Cohen, D. A.; Pearson, J. K., Constraints and universal algebra, Annals of Mathematics and Artificial Intelligence, 24, 51-67 (1998) · Zbl 0930.68143 |
| [22] | Ph.G. Kolaitis, M.Y. Vardi, A game-theoretic approach to constraint satisfaction, in: Proc. 17th National Conference on Artificial Intelligence, AAAI-2000, 2000, pp. 175-181; Ph.G. Kolaitis, M.Y. Vardi, A game-theoretic approach to constraint satisfaction, in: Proc. 17th National Conference on Artificial Intelligence, AAAI-2000, 2000, pp. 175-181 |
| [23] | B. Larose, C. Loten, C. Tardif, A characterisation of first-order constraint satisfaction problems, in: Proc. 21st IEEE Symp. on Logic in Computer Science, 2006, pp. 201-210; B. Larose, C. Loten, C. Tardif, A characterisation of first-order constraint satisfaction problems, in: Proc. 21st IEEE Symp. on Logic in Computer Science, 2006, pp. 201-210 · Zbl 1131.68098 |
| [24] | Larose, B.; Zádori, L., Bounded width problems and algebras, Algebra Universalis, 58, 439-466 (2007) · Zbl 1120.08002 |
| [25] | Libkin, L., Elements of Finite Model Theory (2004), Springer · Zbl 1060.03002 |
| [26] | Mackworth, A. K., Consistency in networks of relations, Artificial Intelligence, 8, 99-118 (1977) · Zbl 0341.68061 |
| [27] | Montanari, U., Networks of constraints: Fundamental properties and applications to picture processing, Information Sciences, 7, 95-132 (1974) · Zbl 0284.68074 |
| [28] | O. Reingold, Undirected st-connectivity in log-space, in: 37th Annual Symposium on Theory of Computing, 2005, pp. 376-385; O. Reingold, Undirected st-connectivity in log-space, in: 37th Annual Symposium on Theory of Computing, 2005, pp. 376-385 · Zbl 1192.68374 |
| [29] | Seymour, P.; Thomas, R., Graph searching and a min-max theorem for treewidth, Journal of Combinatorial Theory, Series B, 58, 22-33 (1993) · Zbl 0795.05110 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
