Document Open Access Logo

Homomorphism Problems for First-Order Definable Structures

Authors Bartek Klin, Slawomir Lasota, Joanna Ochremiak, Szymon Torunczyk

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2016.14.pdf
  • Filesize: 453 kB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • Sets with atoms
  • first-order interpretations
  • homomorphism problem

Metrics

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

Abstract

We investigate several variants of the homomorphism problem: given two relational structures, is there a homomorphism from one to the other? The input structures are possibly infinite, but definable by first-order interpretations in a fixed structure. Their signatures can be either finite or infinite but definable. The homomorphisms can be either arbitrary, or definable with parameters, or definable without parameters. For each of these variants, we determine its decidability status.

Cite As Get BibTex

Bartek Klin, Slawomir Lasota, Joanna Ochremiak, and Szymon Torunczyk. Homomorphism Problems for First-Order Definable Structures. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.14

Author Details

Bartek Klin
Slawomir Lasota
Joanna Ochremiak
Szymon Torunczyk

References

  1. Robert Berger. The undecidability of the domino problem. Mem. Amer. Math. Soc., 66, 1966. Google Scholar
  2. Manuel Bodirsky. Complexity classification in infinite-domain constraint satisfaction. Mémoire d'habilitation àdiriger des recherches, , Université Diderot – Paris 7, Available at arXiv:1201.0856, 2012. Google Scholar
  3. Manuel Bodirsky and Jan Kára. The complexity of equality constraint languages. Theory Comput. Syst., 43(2):136-158, 2008. Google Scholar
  4. Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. J. ACM, 57(2), 2010. Google Scholar
  5. Manuel Bodirsky, Barnaby Martin, and Antoine Mottet. Constraint satisfaction problems over the integers with successor. In Procs. ICALP, volume 9134 of LNCS, pages 256-267, 2015. Google Scholar
  6. Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz. Constraint satisfaction problems for reducts of homogeneous graphs. In Procs. of ICALP'16, 2016. To appear. Google Scholar
  7. Manuel Bodirsky and Antoine Mottet. Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction. In Procs. of LICS'16, 2016. To appear. Google Scholar
  8. Manuel Bodirsky and Jaroslav Nešetřil. Constraint satisfaction with countable homogeneous templates. J. Log. Comput., 16(3):359-373, 2006. Google Scholar
  9. Manuel Bodirsky and Michael Pinsker. Schaefer’s theorem for graphs. In Procs. STOC, pages 655-664, 2011. Google Scholar
  10. Manuel Bodirsky and Michael Pinsker. Topological Birkhoff. Transactions of the AMS, 367:2527-2549, 2015. Google Scholar
  11. Manuel Bodirsky, Michael Pinsker, and Todor Tsankov. Decidability of definability. The Journal of Symbolic Logic, 78(04):1036-1054, 2013. Google Scholar
  12. Manuel Bodirsky and Michal Wrona. Equivalence constraint satisfaction problems. In Procs. CSL, pages 122-136, 2012. Google Scholar
  13. M. Bojańczyk and S. Toruńczyk. Imperative programming in sets with atoms. In Procs. FSTTCS 2012, volume 18 of LIPIcs, 2012. Google Scholar
  14. Mikołaj Bojańczyk, Laurent Braud, Bartek Klin, and Sławomir Lasota. Towards nominal computation. In Procs. POPL 2012, pages 401-412, 2012. Google Scholar
  15. Mikołaj Bojańczyk, Bartek Klin, and Sławomir Lasota. Automata theory in nominal sets. Log. Meth. Comp. Sci., 10, 2014. Google Scholar
  16. Mikołaj Bojańczyk, Bartek Klin, Sławomir Lasota, and Szymon Toruńczyk. Turing machines with atoms. In LICS, pages 183-192, 2013. Google Scholar
  17. Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389-410, 1992. Google Scholar
  18. 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 J. Comput., 28(1):57-104, February 1999. URL: http://dx.doi.org/10.1137/S0097539794266766.
  19. Wilfrid Hodges. Model Theory. Number 42 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1993. Google Scholar
  20. A. S. Kechris, V. G. Pestov, and S. Todorcevic. Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups. Geometric &Functional Analysis GAFA, 15(1):106-189, 2005. Google Scholar
  21. Bartek Klin, Eryk Kopczyński, Joanna Ochremiak, and Szymon Toruńczyk. Locally finite constraint satisfaction problems. In Procs. of LICS'15, pages 475-486, 2015. Google Scholar
  22. Bartek Klin and Michal Szynwelski. SMT solving for functional programming over infinite structures. In Procs. MSFP'16, pages 57-75, 2016. Google Scholar
  23. P. Kolaitis and M. Vardi. The decision problem for the probabilities of higher-order properties. In Procs. STOC'87, pages 425-435, 1987. Google Scholar
  24. Eryk Kopczyński and Szymon Toruńczyk. LOIS: an application of SMT solvers. In Procs. SMT Workshop, volume 1716 of CEUR Proceedings, pages 51-60, 2016. Google Scholar
  25. Jaroslav Nešetřil and Vojtech Rödl. Partitions of finite relational and set systems. Journal of Combinatorial Theory, Series A, 22(3):289-312, 1977. Google Scholar
  26. A. M. Pitts. Nominal Sets: Names and Symmetry in Computer Science. Cambridge University Press, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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