Homomorphism Problems for First-Order Definable Structures
- Klin, Bartek
- Lasota, Slawomir
- Ochremiak, Joanna
- Torunczyk, Szymon
Publication date
January 2016
DOI Publisher
LIPIcs - Leibniz International Proceedings in Informatics. 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)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
Add to ORKG