License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6849/
Go to the corresponding LIPIcs Volume Portal

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

Homomorphism Problems for First-Order Definable Structures

pdf-format:
LIPIcs-FSTTCS-2016-14.pdf (0.4 MB)

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
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI