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

Chen, Hubie ; Mayr, Peter

Quantified Constraint Satisfaction on Monoids

pdf-format:
LIPIcs-CSL-2016-15.pdf (0.5 MB)

Abstract

We contribute to a research program that aims to classify, for each finite structure, the computational complexity of the quantified constraint satisfaction problem on the structure. Employing an established algebraic viewpoint to studying this problem family, whereby this classification program can be phrased as a classification of algebras, we give a complete classification of all finite monoids.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2016:6555,
  author =	{Hubie Chen and Peter Mayr},
  title =	{{Quantified Constraint Satisfaction on Monoids}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{15:1--15:14},
  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/6555},
  URN =		{urn:nbn:de:0030-drops-65553},
  doi =		{10.4230/LIPIcs.CSL.2016.15},
  annote =	{Keywords: quantified constraint satisfaction, universal algebra, computational complexity}
}

Keywords: quantified constraint satisfaction, universal algebra, computational complexity
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