Constraint satisfaction problems with infinite templates. (English) Zbl 1171.03320
Creignou, Nadia (ed.) et al., Complexity of constraints. An overview of current research themes. Berlin: Springer (ISBN 978-3-540-92799-0/pbk). Lecture Notes in Computer Science 5250, 196-228 (2008).
Summary: Allowing templates with infinite domains greatly expands the range of problems that can be formulated as a non-uniform constraint satisfaction problem. It turns out that many CSPs over infinite templates can be formulated with templates that are \(\omega \)-categorical. We survey examples of such problems in temporal and spatial reasoning, infinite-dimensional algebra, acyclic colorings in graph theory, artificial intelligence, phylogenetic reconstruction in computational biology, and tree descriptions in computational linguistics.
We then give an introduction to the universal-algebraic approach to infinite-domain constraint satisfaction, and discuss how cores, polymorphism clones, and pseudo-varieties can be used to study the computational complexity of CSPs with \(\omega \)-categorical templates. The theoretical results will be illustrated by examples from the mentioned application areas. We close with a series of open problems and promising directions of future research.
For the entire collection see [Zbl 1154.68008].
We then give an introduction to the universal-algebraic approach to infinite-domain constraint satisfaction, and discuss how cores, polymorphism clones, and pseudo-varieties can be used to study the computational complexity of CSPs with \(\omega \)-categorical templates. The theoretical results will be illustrated by examples from the mentioned application areas. We close with a series of open problems and promising directions of future research.
For the entire collection see [Zbl 1154.68008].
References:
| [1] | Abian, A.: Categoricity of denumerable atomless boolean rings. Studia Logica 30(1), 63–67 (1972) · Zbl 0268.02032 · doi:10.1007/BF02120830 |
| [2] | Adeleke, S., Neumann, P.M.: Structure of partially ordered sets with transitive automorphism groups. AMS Memoir 57(334) (1985) |
| [3] | Adeleke, S.A., Macpherson, D.: Classification of infinite primitive jordan permutation groups. Proceedings of the London Mathematical Society s3-72(1), 63–123 (1996) · Zbl 0839.20002 · doi:10.1112/plms/s3-72.1.63 |
| [4] | Aho, A., Sagiv, Y., Szymanski, T., Ullman, J.: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing 10(3), 405–421 (1981) · Zbl 0462.68086 · doi:10.1137/0210030 |
| [5] | Allen, J.F.: Maintaining knowledge about temporal intervals. Communications of the ACM 26(11), 832–843 (1983) · Zbl 0519.68079 · doi:10.1145/182.358434 |
| [6] | Bauslaugh, B.L.: The complexity of infinite h-coloring. J. Comb. Theory, Ser. B 61(2), 141–154 (1994) · Zbl 0802.05038 · doi:10.1006/jctb.1994.1040 |
| [7] | Bodirsky, M.: Cores of countably categorical structures. In: Logical Methods in Computer Science, LMCS (2007), doi:10.2168/LMCS-3(1:2) · Zbl 1128.03021 |
| [8] | Bodirsky, M., Chen, H.: Oligomorphic clones. Algebra Universalis 57(1), 109–125 (2007) · Zbl 1121.08005 · doi:10.1007/s00012-007-2026-0 |
| [9] | Bodirsky, M., Chen, H.: Qualitative temporal and spatial reasoning revisited. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646, pp. 194–207. Springer, Heidelberg (2007) · Zbl 1179.68150 · doi:10.1007/978-3-540-74915-8_17 |
| [10] | Bodirsky, M., Chen, H., Kara, J., von Oertzen, T.: Maximal infinite-valued constraint languages. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 546–557. Springer, Heidelberg (2007) · Zbl 1171.68722 · doi:10.1007/978-3-540-73420-8_48 |
| [11] | Bodirsky, M., Dalmau, V.: Datalog and constraint satisfaction with infinite templates. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 646–659. Springer, Heidelberg (2006) · Zbl 1136.03314 · doi:10.1007/11672142_53 |
| [12] | Bodirsky, M., Kára, J.: The complexity of equality constraint languages. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol. 3967, pp. 114–126. Springer, Heidelberg (2006) · Zbl 1148.68385 · doi:10.1007/11753728_14 |
| [13] | Bodirsky, M., Kára, J.: The complexity of temporal constraint satisfaction problems (preprint, 2007) |
| [14] | Bodirsky, M., Kára, J.: A fast algorithm and lower bound for temporal reasoning (preprint, 2007) |
| [15] | Bodirsky, M., Kutz, M.: Pure dominance constraints. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. 2285, pp. 287–298. Springer, Heidelberg (2002) · Zbl 1054.68700 · doi:10.1007/3-540-45841-7_23 |
| [16] | Bodirsky, M., Kutz, M.: Determining the consistency of partial tree descriptions. Artificial Intelligence 171, 185–196 (2007) · Zbl 1168.68546 · doi:10.1016/j.artint.2006.12.004 |
| [17] | Bodirsky, M., Nešetřil, J.: Constraint satisfaction with countable homogeneous templates. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol. 2803, pp. 44–57. Springer, Heidelberg (2003) · Zbl 1116.03313 · doi:10.1007/978-3-540-45220-1_5 |
| [18] | Bodnarčuk, V.G., Kalužnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for post algebras, part I and II. Cybernetics 5, 243–539 (1969) · doi:10.1007/BF01070906 |
| [19] | Broxvall, M., Jonsson, P.: Point algebras for temporal reasoning: Algorithms and complexity. Artif. Intell. 149(2), 179–220 (2003) · Zbl 1082.68817 · doi:10.1016/S0004-3702(03)00075-4 |
| [20] | Bulatov, A.: A graph of a relational structure and constraint satisfaction problems. In: Proceedings of the 19th IEEE Annual Symposium on Logic in Computer Science (LICS 2004), Turku, Finland (2004) · doi:10.1109/LICS.2004.1319639 |
| [21] | Bulatov, A., Jeavons, P.: Algebraic structures in combinatorial problems. Technical report MATH-AL-4-2001, Technische Universitat Dresden. International Journal of Algebra and Computing (submitted, 2001) |
| [22] | Bulatov, A., Krokhin, A., Jeavons, P.G.: Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing 34, 720–742 (2005) · Zbl 1071.08002 · doi:10.1137/S0097539700376676 |
| [23] | Bulatov, A.A., Dalmau, V.: A simple algorithm for Mal’tsev constraints. SIAM J. Comput. 36(1), 16–27 (2006) · Zbl 1112.08002 · doi:10.1137/050628957 |
| [24] | Burris, S., Sankappanavar, H.: A Course in Universal Algebra. Springer, Berlin (1981) · Zbl 0478.08001 · doi:10.1007/978-1-4613-8130-3 |
| [25] | Cameron, P.J.: Oligomorphic Permutation Groups. Cambridge Univ. Press, Cambridge (1990) · Zbl 0813.20002 · doi:10.1017/CBO9780511549809 |
| [26] | Cherlin, G., Harrington, L., Lachlan, A.: \(\aleph_0\) -categorical, \(\aleph_0\) -stable structures. Annals of Pure and Applied Logic 28, 103–135 (1985) · Zbl 0566.03022 · doi:10.1016/0168-0072(85)90023-5 |
| [27] | Cherlin, G., Hrushovski, E.: Finite Structures with Few Types. Princeton University Press, Princeton (2003) · Zbl 1024.03001 |
| [28] | Cherlin, G., Lachlan, A.H.: Stable finitely homogeneous structures. TAMS 296, 815–850 (1986) · Zbl 0641.03022 · doi:10.1090/S0002-9947-1986-0846608-8 |
| [29] | Cohen, D., Jeavons, P., Jonsson, P., Koubarakis, M.: Building tractable disjunctive constraints. Journal of the ACM 47(5), 826–853 (2000) · Zbl 1320.68169 · doi:10.1145/355483.355485 |
| [30] | Droste, M.: Structure of partially ordered sets with transitive automorphism groups. AMS Memoir 57(334) (1985) · Zbl 0574.06001 |
| [31] | Düntsch, I.: Relation algebras and their application in temporal and spatial reasoning. Artificial Intelligence Review 23, 315–357 (2005) · Zbl 1105.68099 · doi:10.1007/s10462-004-5899-8 |
| [32] | Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999) · Zbl 0932.03032 |
| [33] | Evans, D.: Examples of \(\aleph_0\) -categorical structures. In: Kaye, R., Macpherson, H.D. (eds.) Automorphisms of first-order structures, pp. 33–72. Oxford University Press, Oxford (1994) · Zbl 0812.03016 |
| [34] | Feder, T., Hell, P., Mohar, B.: Acyclic homomorphisms and circular colorings of digraphs. SIAM J. Discrete Math. 17(1), 161–169 (2003) · Zbl 1034.05022 · doi:10.1137/S0895480103422184 |
| [35] | Feder, T., Vardi, M.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing 28, 57–104 (1999) · Zbl 0914.68075 · doi:10.1137/S0097539794266766 |
| [36] | Fraïssé, R.: Theory of Relations. North-Holland, Amsterdam (1986) · Zbl 0593.04001 |
| [37] | Garey, M., Johnson, D.: A guide to NP-completeness. CSLI Press (1978) · Zbl 0379.68035 |
| [38] | Geiger, D.: Closed systems of functions and predicates. Pacific Journal of Mathematics 27, 95–100 (1968) · Zbl 0186.02502 · doi:10.2140/pjm.1968.27.95 |
| [39] | Goldstern, M., Pinsker, M.: A survey of clones on infinite sets. arXiv:0701030 (preprint, 2007) · Zbl 1201.08003 |
| [40] | Hell, P., Nešetřil, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Series B 48, 92–110 (1990) · Zbl 0639.05023 · doi:10.1016/0095-8956(90)90132-J |
| [41] | Hirsch, R.: Expressive power and complexity in algebraic logic. Journal of Logic and Computation 7(3), 309–351 (1997) · Zbl 0874.03051 · doi:10.1093/logcom/7.3.309 |
| [42] | Hodges, W.: A shorter model theory. Cambridge University Press, Cambridge (1997) · Zbl 0873.03036 |
| [43] | Idziak, P.M., Markovic, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebras with few subpowers. In: LICS, pp. 213–224 (2007) · Zbl 1216.68129 · doi:10.1109/LICS.2007.50 |
| [44] | Jonsson, P., Drakengren, T.: A complete classification of tractability in RCC-5. J. Artif. Intell. Res. 6, 211–221 (1997) · Zbl 0894.68096 |
| [45] | Kantor, W.M., Macpherson, H.D., Liebeck, M.W.: \(\aleph_0\) -categorical structures smoothly approximated by finite substructures. Proc. London Math. Soc. 59, 439–463 (1989) · Zbl 0649.03018 · doi:10.1112/plms/s3-59.3.439 |
| [46] | Keisler, J.: Reduced products and Horn classes. Trans. Amer. Math. Soc. 117, 307–328 (1965) · Zbl 0199.01103 · doi:10.1090/S0002-9947-1965-0170812-4 |
| [47] | Klíma, O., Tesson, P., Thérien, D.: Dichotomies in the complexity of solving systems of equations over finite semigroups. Theory Comput. Syst. 40(3), 263–297 (2007) · Zbl 1109.68051 · doi:10.1007/s00224-005-1279-2 |
| [48] | Koubarakis, M.: Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning. Theoretical Computer Science 266, 311–339 (2001) · Zbl 0989.68134 · doi:10.1016/S0304-3975(00)00177-8 |
| [49] | Krokhin, A.A., Jeavons, P., Jonsson, P.: Reasoning about temporal relations: The tractable subalgebras of Allen’s interval algebra. JACM 50(5), 591–640 (2003) · Zbl 1325.68220 · doi:10.1145/876638.876639 |
| [50] | Kun, G.: Constraints, mmsnp, and expander relational structures. arXiv:0706.1701 (2007) · Zbl 1313.05274 |
| [51] | Lachlan, A.H.: Stable finitely homogeneous structures: A survey. In: Algebraic Model Theory, NATO ASI Series, vol. 496, pp. 145–159 (1996) · Zbl 0878.03024 |
| [52] | Ladner, R.E.: On the structure of polynomial time reducibility. JACM 22(1), 155–171 (1975) · Zbl 0322.68028 · doi:10.1145/321864.321877 |
| [53] | Macpherson, D.: A survey of jordan groups. In: Kaye, R., Macpherson, H.D. (eds.) Automorphisms of first-order structures, pp. 73–110. Oxford University Press, Oxford (1994) · Zbl 0824.20003 |
| [54] | Matiyasevich, Y.: Enumerable sets are diophantine. Doklady Akademii Nauk SSSR 191, 279–282 (1970) · Zbl 0212.33401 |
| [55] | Nebel, B., Bürckert, H.-J.: Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra. JACM 42(1), 43–66 (1995) · Zbl 0886.68077 · doi:10.1145/200836.200848 |
| [56] | Paterson, M.S., Wegman, M.N.: Linear unification. Journal of Computer and System Sciences 16, 158–167 (1978) · Zbl 0371.68013 · doi:10.1016/0022-0000(78)90043-0 |
| [57] | Poizat, B.: A Course in Model Theory: An Introduction to Contemporary Mathematical Logic. Springer, Heidelberg (2000) · Zbl 0951.03002 · doi:10.1007/978-1-4419-8622-1 |
| [58] | Renz, J., Nebel, B.: On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus. Artif. Intell. 108(1-2), 69–123 (1999) · Zbl 0914.68160 · doi:10.1016/S0004-3702(99)00002-8 |
| [59] | Szendrei, A.: Clones in universal Algebra. Seminaire de mathematiques superieures. Les Presses de L’Universite de Montreal (1986) · Zbl 0603.08004 |
| [60] | van Beek, P., Cohen, R.: Exact and approximate reasoning about temporal relations. Computational Intelligence 6, 132–144 (1990) · doi:10.1111/j.1467-8640.1990.tb00130.x |
| [61] | Zilber, B.: Uncountable categorical theories, Tranlations of Mathematical Monographs, vol. 117. Amer. Math. Soc. (1993) · Zbl 0785.03019 |
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.
