Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.14
URN: urn:nbn:de:0030-drops-68498
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6849/
Klin, Bartek ; Lasota, Slawomir ; Ochremiak, Joanna ; Torunczyk, Szymon
Homomorphism Problems for First-Order Definable Structures
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{klin_et_al:LIPIcs:2016:6849,
author = {Bartek Klin and Slawomir Lasota and Joanna Ochremiak and Szymon Torunczyk},
title = {{Homomorphism Problems for First-Order Definable Structures}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-027-9},
ISSN = {1868-8969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6849},
URN = {urn:nbn:de:0030-drops-68498},
doi = {10.4230/LIPIcs.FSTTCS.2016.14},
annote = {Keywords: Sets with atoms, first-order interpretations, homomorphism problem}
}
| Keywords: | Sets with atoms, first-order interpretations, homomorphism problem | |
| Seminar: | 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 10.12.2016 |
