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

Mary, Arnaud ; Strozecki, Yann

Efficient Enumeration of Solutions Produced by Closure Operations

pdf-format:
53.pdf (0.7 MB)

Abstract

In this paper we address the problem of generating all elements obtained by the saturation of an initial set by some operations. More precisely, we prove that we can generate the closure by polymorphisms of a boolean relation with a polynomial delay. Therefore we can compute with polynomial delay the closure of a family of sets by any set of "set operations" (e.g. by union, intersection, difference, symmetric difference ...). To do so, we prove that for any set of operations F, one can decide in polynomial time whether an element belongs to the closure by F of a family of sets. When the relation is over a domain larger than two elements, we prove that our generic enumeration method fails, since the associated decision problem is NP-hard.

BibTeX - Entry

@InProceedings{mary_et_al:LIPIcs:2016:5753,
  author =	{Arnaud Mary and Yann Strozecki},
  title =	{{Efficient Enumeration of Solutions Produced by Closure Operations}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{52:1--52:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5753},
  URN =		{urn:nbn:de:0030-drops-57538},
  doi =		{10.4230/LIPIcs.STACS.2016.52},
  annote =	{Keywords: enumeration, set saturation, polynomial delay, Post’s lattice}
}

Keywords: enumeration, set saturation, polynomial delay, Post’s lattice
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

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