×
Bodirsky, Manuel; Rydval, Jakub

On the descriptive complexity of temporal constraint satisfaction problems. (English) Zbl 07876155

J. ACM 70, No. 1, Paper No. 2, 58 p. (2023).

MSC:

68-XX Computer science

Keywords:

temporal constraint satisfaction problems; fixed-point logic; Maltsev conditions
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Atserias, A.. 2008. On digraph coloring problems and treewidth duality. European Journal of Combinatorics29, 4 (2008), 796-820. · Zbl 1160.05024
[2] Atserias, A., Bulatov, A., and Dawar, A.. 2009. Affine systems of equations and counting infinitary logic. Theoretical Computer Science410, 18 (2009), 1666-1683. · Zbl 1168.68040
[3] Atserias, A. and Dawar, A.. 2019. Definable inapproximability: New challenges for duplicator. Journal of Logic and Computation29, 8 (2019), 1185-1210. · Zbl 1446.68072
[4] Barto, L., Bulín, J., Krokhin, A., and Opršal, J.. 2021. Algebraic approach to promise constraint satisfaction. Journal of the ACM68, 4 (2021), 1-66. · Zbl 1499.68140
[5] Barto, L., Kompatscher, M., Olšák, M., Van Pham, T., and Pinsker, M.. 2019. Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \) -categorical structures. Journal of Mathematical Logic19, 2 (2019), 1-31. · Zbl 1477.03118
[6] Barto, L. and Kozik, M.. 2014. Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM61, 1 (2014), 1-19. · Zbl 1295.68126
[7] Barto, L., Krokhin, A., and Willard, R.. 2017. Polymorphisms, and how to use them. In The Constraint Satisfaction Problem: Complexity and Approximability, A. Krokhin and S. Živný (Eds.). , Vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 1-44. · Zbl 1482.68161
[8] Barto, L., Opršal, J., and Pinsker, M.. 2018. The wonderland of reflections. Israel Journal of Mathematics223, 1 (2018), 363-398. · Zbl 1397.08002
[9] Blass, A., Gurevich, Y., and Shelah, S.. 2002. On polynomial time computation over unordered structures. Journal of Symbolic Logic67, 3 (2002), 1093-1125. · Zbl 1020.03038
[10] Bodirsky, M.. 2021. Complexity of Infinite-Domain Constraint Satisfaction. Cambridge University Press, Cambridge, UK. · Zbl 1495.68007
[11] Bodirsky, M., Chen, H., and Wrona, M.. 2014. Tractability of quantified temporal constraints to the max. International Journal of Algebra and Computation24, 08 (2014), 1141-1156. · Zbl 1320.68097
[12] Bodirsky, M. and Dalmau, V.. 2013. Datalog and constraint satisfaction with infinite templates. Journal of Computer and System Sciences79, 1 (2013), 79-100. · Zbl 1263.68051
[13] Bodirsky, M. and Kára, J.. 2008. The complexity of equality constraint languages. Theory of Computing Systems43, 2 (2008), 136-158. · Zbl 1148.68025
[14] Bodirsky, M. and Kára, J.. 2010. The complexity of temporal constraint satisfaction problems. Journal of the ACM57, 2 (2010), 9. · Zbl 1327.68125
[15] Bodirsky, M. and Kára, J.. 2010. A fast algorithm and Datalog inexpressibility for temporal reasoning. ACM Transactions on Computational Logic11, 3 (2010), 1-21. · Zbl 1351.68051
[16] Bodirsky, M. and Mottet, A.. 2016. Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’16). ACM, New York, NY, 623-632. · Zbl 1401.68109
[17] Bodirsky, M., Mottet, A., Olšák, M., Opršal, J., Pinsker, M., and Willard, R.. 2019. Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems). In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’19). ACM, New York, NY, 1-12.
[18] Bodirsky, M. and Nešetřil, J.. 2006. Constraint satisfaction with countable homogeneous templates. Journal of Logic and Computation16, 3 (2006), 359-373. · Zbl 1113.03026
[19] Bodirsky, M. and Pinsker, M.. 2011. Reducts of Ramsey structures. AMS Contemporary Mathematics558 (2011), 489-519. · Zbl 1261.03118
[20] Bodirsky, M. and Pinsker, M.. 2015. Topological Birkhoff. Transactions of the American Mathematical Society367, 4 (2015), 2527-2549. · Zbl 1375.03032
[21] Bodirsky, M. and Pinsker, M.. 2021. Canonical functions: A proof via topological dynamics. Contributions to Discrete Mathematics16, 2 (2021), 36-45. · Zbl 1537.03031
[22] Cai, J.-Y., Fürer, M., and Immerman, N.. 1992. An optimal lower bound on the number of variables for graph identification. Combinatorica12, 4 (1992), 389-410. · Zbl 0785.68043
[23] Chandra, A. K. and Merlin, P. M.. 1977. Optimal implementation of conjunctive queries in relational databases. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC’77). ACM, New York, NY, 77-90.
[24] Cherlin, G., Shelah, S., and Shi, N.. 1999. Universal graphs with forbidden subgraphs and algebraic closure. Advances in Applied Mathematics22, 4 (1999), 454-491. · Zbl 0928.03049
[25] Dawar, A.. 2015. The nature and power of fixed-point logic with counting. ACM SIGLOG News2, 1 (2015), 8-21.
[26] Dawar, A., Grohe, M., Holm, B., and Laubner, B.. 2009. Logics with rank operators. In Proceedings of the 24th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’09). ACM, New York, NY, 113-122.
[27] Dawar, A. and Kreutzer, S.. 2008. On Datalog vs. LFP. In Automata, Languages and Programming. Lecture Notes in Computer Science, Vol. 5126. Springer, 160-171. · Zbl 1155.68402
[28] Dawar, A. and Wang, P.. 2017. Definability of semidefinite programming and Lasserre lower bounds for CSPs. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’17). ACM, New York, NY, 1-12. · Zbl 1452.90240
[29] Feder, T. and Vardi, M. Y.. 1998. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing28, 1 (1998), 57-104. · Zbl 0914.68075
[30] Feder, T. and Vardi, M. Y.. 2003. Homomorphism closed vs. existential positive. In Proceedings of the 18th Annual ACM/IEEE Symposium of Logic in Computer Science (LICS’03). ACM, New York, NY, 311-320.
[31] Gillibert, P., Jonušas, J., Kompatscher, M., Mottet, A., and Pinsker, M.. 2022. When symmetries are not enough: A hierarchy of hard constraint satisfaction problems. SIAM Journal on Computing51, 2 (2022), 175-213. · Zbl 1483.68141
[32] Goerdt, A.. 2009. On random ordering constraints. In Proceedings of the International Computer Science Symposium in Russia. 105-116. · Zbl 1248.68454
[33] Grädel, E., Grohe, M., Pago, B., and Pakusa, W.. 2019. A finite-model-theoretic view on propositional proof complexity. Logical Methods in Computer Science15, 1 (2019), Article 4, 53 pages. · Zbl 1451.03023
[34] Grädel, E., Kolaitis, P. G., Libkin, L., Marx, M., Spencer, J., Vardi, M. Y., Venema, Y., and Weinstein, S.. 2007. Finite Model Theory and Its Applications. Springer, Berlin, Germany. · Zbl 1133.03001
[35] Grädel, E. and Otto, M.. 1992. Inductive definability with counting on finite structures. In Selected Papers from the 6th International Workshop on Computer Science Logic (CSL’92). Springer-Verlag, Berlin, Germany, 231-247. · Zbl 0792.68061
[36] Grädel, E. and Pakusa, W.. 2019. Rank logic is dead, long live rank logic!Journal of Symbolic Logic84, 1 (2019), 54-87. · Zbl 1425.68134
[37] Grohe, M.. 2008. The quest for a logic capturing PTIME. In Proceedings of the 23rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’08). ACM, New York, NY, 267-271.
[38] Gurevich, Y. and Shelah, S.. 1996. On finite rigid structures. Journal of Symbolic Logic61, 2 (1996), 549-562. · Zbl 0860.03029
[39] Guruswami, V., Håstad, J., Manokaran, R., Raghavendra, P., and Charikar, M.. 2011. Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM Journal on Computing40, 3 (2011), 878-914. · Zbl 1235.68075
[40] Hodges, W.. 1997. A Shorter Model Theory. Cambridge University Press, Cambridge, UK. · Zbl 0873.03036
[41] Hubička, J. and Nešetřil, J.. 2016. Homomorphism and embedding universal structures for restricted classes.Journal of Multiple-Valued Logic & Soft Computing27 (2016), 229-253. · Zbl 1394.03058
[42] Kolaitis, P. G. and Vardi, M. Y.. 2000. Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences61, 2 (2000), 302-332. · Zbl 0963.68059
[43] Kozik, M., Krokhin, A., Valeriote, M., and Willard, R.. 2015. Characterizations of several Maltsev conditions. Algebra Universalis73, 3-4 (2015), 205-224. · Zbl 1319.08002
[44] Kreutzer, S.. 2004. Expressive equivalence of least and inflationary fixed-point logic. Annals of Pure and Applied Logic130, 1-3 (2004), 61-78. · Zbl 1052.03012
[45] Larose, B., Valeriote, M., and Zádori, L.. 2009. Omitting types, bounded width and the ability to count. International Journal of Algebra and Computation19, 5 (2009), 647-668. · Zbl 1178.68289
[46] Larose, B. and Zádori, L.. 2007. Bounded width problems and algebras. Algebra Universalis56, 3-4 (2007), 439-466. · Zbl 1120.08002
[47] Libkin, L.. 2013. Elements of Finite Model Theory. Springer, Berlin, Germany. · Zbl 1060.03002
[48] Lichter, M.. 2021. Separating rank logic from polynomial time. In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’21). ACM, New York, NY, 1-13.
[49] Maróti, M. and McKenzie, R.. 2008. Existence theorems for weakly symmetric operations. Algebra Universalis59, 3 (2008), 463-489. · Zbl 1186.08003
[50] N. Burris, S. and P. Sankappanavar, H.. 1981. A Course in Universal Algebra. Springer-Verlag, Berlin, Germany. · Zbl 0478.08001
[51] Nebel, B. and Bürckert, H.-J.. 1995. Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra. Journal of the ACM42, 1 (1995), 43-66. · Zbl 0886.68077
[52] Olšák, M.. 2019. Generalizing CSP-Related Results to Infinite Algebras. Ph.D. Thesis. Univerzita Karlova, Matematicko-fyzikální fakulta.
[53] Olšák, Miroslav. 2021. Maltsev conditions for general congruence meet-semidistributive algebras. Journal of Symbolic Logic86, 4 (2021), 1432-1451. · Zbl 1487.08002
[54] Otto, M.. 2000. Bounded Variable Logics and Counting: A Study in Finite Model Theory. Springer, Berlin, Germany.
[55] Pakusa, W.. 2015. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. . RWTH Aachen.
[56] Rossman, B.. 2008. Homomorphism preservation theorems. Journal of the ACM55, 3 (2008), 53. · Zbl 1326.03038
[57] Wang, P.. 2018. Descriptive Complexity of Constraint Problems. . University of Cambridge.
[58] Zhuk, D.. 2021. Strong subalgebras and the constraint satisfaction problem.Journal of Multiple-Valued Logic & Soft Computing36, 4 (2021), 455-504. · Zbl 1529.08020
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.