License
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://drops.dagstuhl.de/opus/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
Seminar: 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Issue Date: 2016
Date of publication: 25.08.2016


DROPS-Home | Fulltext Search | Imprint Published by LZI