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.CSL.2016.14
URN: urn:nbn:de:0030-drops-65548
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6554/
Go to the corresponding LIPIcs Volume Portal

Hella, Lauri ; Kolaitis, Phokion G.

Dependence Logic vs. Constraint Satisfaction

pdf-format:
LIPIcs-CSL-2016-14.pdf (0.6 MB)

Abstract

During the past decade, dependence logic has emerged as a formalism suitable for expressing and analyzing notions of dependence and independence that arise in different scientific areas. The sentences of dependence logic have the same expressive power as those of existential second-order logic, hence dependence logic captures NP on the class of all finite structures. In this paper, we identify a natural fragment of universal dependence logic and show that, in a precise sense, it captures constraint satisfaction. This tight connection between dependence logic and constraint satisfaction contributes to the descriptive complexity of constraint satisfaction and elucidates the expressive power of universal dependence logic.

BibTeX - Entry

@InProceedings{hella_et_al:LIPIcs:2016:6554,
  author =	{Lauri Hella and Phokion G. Kolaitis},
  title =	{{Dependence Logic vs. Constraint Satisfaction}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Jean-Marc Talbot and Laurent Regnier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6554},
  URN =		{urn:nbn:de:0030-drops-65548},
  doi =		{10.4230/LIPIcs.CSL.2016.14},
  annote =	{Keywords: Dependence logic, constraint satisfaction, computational complexity, expressive power}
}

Keywords: Dependence logic, constraint satisfaction, computational complexity, expressive power
Collection: 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Issue Date: 2016
Date of publication: 29.08.2016

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