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: https://drops.dagstuhl.de/opus/volltexte/2011/3231/
Durand, Arnaud ; Strozecki, Yann
Enumeration Complexity of Logical Query Problems with Second-order Variables
| pdf-format: |
|
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 | |
| Seminar: | Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL | |
| Issue date: | 2011 | |
| Date of publication: | 31.08.2011 |
