Document Open Access Logo

Network Satisfaction Problems Solved by k-Consistency

Authors Manuel Bodirsky , Simon Knäuer

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2023.116.pdf
  • Filesize: 0.81 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Complexity theory and logic
Keywords
  • Constraint Satisfaction
  • Computational Complexity
  • Relation Algebras
  • Network Satisfaction
  • Qualitative Reasoning
  • k-Consistency
  • Datalog

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We show that the problem of deciding for a given finite relation algebra A whether the network satisfaction problem for A can be solved by the k-consistency procedure, for some k ∈ ℕ, is undecidable. For the important class of finite relation algebras A with a normal representation, however, the decidability of this problem remains open. We show that if A is symmetric and has a flexible atom, then the question whether NSP(A) can be solved by k-consistency, for some k ∈ ℕ, is decidable (even in polynomial time in the number of atoms of A). This result follows from a more general sufficient condition for the correctness of the k-consistency procedure for finite symmetric relation algebras. In our proof we make use of a result of Alexandr Kazda about finite binary conservative structures.

Cite As Get BibTex

Manuel Bodirsky and Simon Knäuer. Network Satisfaction Problems Solved by k-Consistency. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 116:1-116:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.116

Author Details

Manuel Bodirsky
  • Institut für Algebra, TU Dresden, Germany
Simon Knäuer
  • Institut für Algebra, TU Dresden, Germany

Funding

  • Bodirsky, Manuel: The author has received funding from the European Union (ERC Grant NO. 681988, CSP-Infinity and ERC Synergy Grant No. 101071674, POCOCOP).
  • Knäuer, Simon: The author was supported by DFG Graduiertenkolleg 1763 (QuantLA).

References

  1. Jeremy F. Alm, Roger D. Maddux, and Jacob Manske. Chromatic graphs, Ramsey numbers and the flexible atom conjecture. The Electronic Journal of Combinatorics, 15(1), March 2008. URL: https://doi.org/10.37236/773.
  2. Albert Atserias, Andrei A. Bulatov, and Víctor Dalmau. On the power of k-consistency. In ICALP, pages 279-290, 2007. Google Scholar
  3. Libor Barto. The dichotomy for conservative constraint satisfaction problems revisited. In Proceedings of the Symposium on Logic in Computer Science (LICS), Toronto, Canada, 2011. Google Scholar
  4. Libor Barto and Marcin Kozik. Constraint satisfaction problems of bounded width. In Proceedings of Symposium on Foundations of Computer Science (FOCS), pages 595-603, 2009. Google Scholar
  5. Libor Barto and Marcin Kozik. Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM, 61(1):3:1-3:19, 2014. Google Scholar
  6. Manuel Bodirsky. Complexity classification in infinite-domain constraint satisfaction. Mémoire d'habilitation à diriger des recherches, Université Diderot - Paris 7. Available at https://arxiv.org/abs/1201.0856v8, 2012.
  7. Manuel Bodirsky. Finite relation algebras with normal representations. In Relational and Algebraic Methods in Computer Science - 17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29 - November 1, 2018, Proceedings, pages 3-17, 2018. Google Scholar
  8. Manuel Bodirsky and Víctor Dalmau. Datalog and constraint satisfaction with infinite templates. Journal on Computer and System Sciences, 79:79-100, 2013. A preliminary version appeared in the proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS'05). Google Scholar
  9. Manuel Bodirsky and Peter Jonsson. A model-theoretic view on qualitative constraint reasoning. Journal of Artificial Intelligence Research, 58:339-385, 2017. Google Scholar
  10. Manuel Bodirsky and Simon Knäuer. Hardness of network satisfaction for relation algebras with normal representations. In Relational and Algebraic Methods in Computer Science, pages 31-46. Springer International Publishing, 2020. URL: https://doi.org/10.1007/978-3-030-43520-2_3.
  11. Manuel Bodirsky and Simon Knäuer. Network satisfaction for symmetric relation algebras with a flexible atom. In Proceedings of AAAI, 2021. Preprint https://arxiv.org/abs/2008.11943. Google Scholar
  12. Manuel Bodirsky and Simon Knäuer. The complexity of network satisfaction problems for symmetric relation algebras with a flexible atom. Journal of Artificial Intelligence Research, 75:1701-1744, December 2022. URL: https://doi.org/10.1613/jair.1.14195.
  13. Manuel Bodirsky and Simon Knäuer. Network satisfaction problems solved by k-consistency, 2023. Google Scholar
  14. Manuel Bodirsky and Antoine Mottet. A dichotomy for first-order reducts of unary structures. Logical Methods in Computer Science, 14(2), 2018. URL: https://doi.org/10.23638/LMCS-14(2:13)2018.
  15. V. G. Bodnarčuk, L. A. Kalužnin, V. N. Kotov, and B. A. Romov. Galois theory for Post algebras, part I and II. Cybernetics, 5:243-539, 1969. Google Scholar
  16. Andrei A. Bulatov. Tractable conservative constraint satisfaction problems. In Proceedings of the Symposium on Logic in Computer Science (LICS), pages 321-330, Ottawa, Canada, 2003. Google Scholar
  17. Andrei A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Logic, 12(4), July 2011. URL: https://doi.org/10.1145/1970398.1970400.
  18. Andrei A. Bulatov. Conservative constraint satisfaction re-revisited. Journal Computer and System Sciences, 82(2):347-356, 2016. ArXiv:1408.3690. URL: https://doi.org/10.1016/j.jcss.2015.07.004.
  19. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, pages 319-330, 2017. Google Scholar
  20. Hubie Chen and Benoît Larose. Asking the metaquestions in constraint tractability. TOCT, 9(3):11:1-11:27, 2017. Google Scholar
  21. Matteo Cristiani and Robin Hirsch. The complexity of the constraint satisfaction problem for small relation algebras. Artificial Intelligence Journal, 156:177-196, 2004. Google Scholar
  22. Ivo Düntsch. Relation algebras and their application in temporal and spatial reasoning. Artificial Intelligence Review, 23:315-357, 2005. Google Scholar
  23. Tomás Feder and Moshe Y. Vardi. 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. Google Scholar
  24. David Geiger. Closed systems of functions and predicates. Pacific Journal of Mathematics, 27:95-100, 1968. Google Scholar
  25. R. Hirsch and I. Hodkinson. Representability is not decidable for finite relation algebras. Transactions of the American Mathematical Society, 353(4):1387-1401), 2001. Google Scholar
  26. R. Hirsch and I. Hodkinson. Strongly representable atom structures of relation algebras. Transactions of the American Mathematical Society, 130(6):1819-1831), 2001. Google Scholar
  27. Robin Hirsch. Relation algebras of intervals. Artificial Intelligence Journal, 83:1-29, 1996. Google Scholar
  28. Robin Hirsch. Expressive power and complexity in algebraic logic. Journal of Logic and Computation, 7(3):309-351, 1997. Google Scholar
  29. Robin Hirsch. A finite relation algebra with undecidable network satisfaction problem. Logic Journal of the IGPL, 7(4):547-554, 1999. Google Scholar
  30. Robin Hirsch and Ian Hodkinson. Relation Algebras by Games. North Holland, 2002. Google Scholar
  31. Alexandr Kazda. CSP for binary conservative relational structures. Algebra universalis, 75(1):75-84, December 2015. URL: https://doi.org/10.1007/s00012-015-0358-8.
  32. Simon Knäuer. Constraint Network Satisfaction for Finite Relation Algebras. PhD thesis, Technische Universität Dresden, 2023. Google Scholar
  33. Marcin Kozik, Andrei Krokhin, Matt Valeriote, and Ross Willard. Characterizations of several Maltsev conditions. Algebra universalis, 73(3):205-224, 2015. URL: https://doi.org/10.1007/s00012-015-0327-2.
  34. R. Lyndon. The representation of relational algebras. Annals of Mathematics, 51(3):707-729, 1950. Google Scholar
  35. Roger D. Maddux. A perspective on the theory of relation algebras. Algebra Universalis, 31(3):456-465, September 1994. URL: https://doi.org/10.1007/bf01221799.
  36. Roger D. Maddux. Relation Algebras: Volume 150. Studies in logic and the foundations of mathematics. Elsevier Science, London, England, May 2006. Google Scholar
  37. Ralph McKenzie. The representation of relation algebras. PhD thesis, University of Colorado at Boulder, 1966. Google Scholar
  38. Ralph McKenzie. Representations of integral relation algebras. Michigan Mathematical Journal, 17(3):279-287, 1970. URL: https://doi.org/10.1307/mmj/1029000477.
  39. Antoine Mottet, Tomás Nagy, Michael Pinsker, and Michal Wrona. Smooth approximations and relational width collapses. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 138:1-138:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.138.
  40. Jochen Renz and Bernhard Nebel. Qualitative spatial reasoning using constraint calculi. In M. Aiello, I. Pratt-Hartmann, and J. van Benthem, editors, Handbook of Spatial Logics, pages 161-215. Springer Verlag, Berlin, 2007. Google Scholar
  41. Alfred Tarski. Representation problems for relation algebras. Bulletin of the AMS, 54(80), 1948. Google Scholar
  42. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1-30:78, 2020. URL: https://doi.org/10.1145/3402029.
  43. Dmitriy N. Zhuk. A proof of CSP dichotomy conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, pages 331-342, 2017. https://arxiv.org/abs/1704.01914. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact