2026-07-22T16:01:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6849 2024-03-06T10:39:01Z ddc:004 open_access

Homomorphism Problems for First-Order Definable Structures Klin, Bartek Lasota, Slawomir Ochremiak, Joanna Torunczyk, Szymon Sets with atoms first-order interpretations homomorphism problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bartek Klin and Slawomir Lasota and Joanna Ochremiak and Szymon Torunczyk 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.14 urn:nbn:de:0030-drops-68498 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.14 eng https://creativecommons.org/licenses/by/3.0/legalcode