The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2011.189
URN: urn:nbn:de:0030-drops-32313
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3231/
Go to the corresponding LIPIcs Volume Portal

Durand, Arnaud ; Strozecki, Yann

Enumeration Complexity of Logical Query Problems with Second-order Variables

pdf-format:
18.pdf (0.5 MB)

Abstract

We consider query problems defined by first order formulas of the form F(x,T) with free first order and second order variables and study the data complexity of enumerating results of such queries. By considering the number of alternations in the quantifier prefixes of formulas, we show that such query problems either admit a constant delay or a polynomial delay enumeration algorithm or are hard to enumerate.
We also exhibit syntactically defined fragments inside the hard cases that still admit good enumeration algorithms and discuss the case of some restricted classes of database structures as inputs.

BibTeX - Entry

@InProceedings{durand_et_al:LIPIcs:2011:3231,
  author =	{Arnaud Durand and Yann Strozecki},
  title =	{{Enumeration Complexity of Logical Query Problems with Second-order Variables}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{189--202},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Marc Bezem},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3231},
  URN =		{urn:nbn:de:0030-drops-32313},
  doi =		{10.4230/LIPIcs.CSL.2011.189},
  annote =	{Keywords: descriptive complexity, enumeration, query problem}
}

Keywords: descriptive complexity, enumeration, query problem
Collection: Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL
Issue Date: 2011
Date of publication: 31.08.2011

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