LIPIcs.CSL.2011.189.pdf
- Filesize: 0.53 MB
- 14 pages
Document
Enumeration Complexity of Logical Query Problems with Second-order Variables
Authors
-
Part of:
Volume:
Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (CSL 2011)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2011-08-31
Cite As Get BibTex
Arnaud Durand and Yann Strozecki. Enumeration Complexity of Logical Query Problems with Second-order Variables. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 189-202, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.CSL.2011.189
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.
Subject Classification
Keywords
- descriptive complexity
- enumeration
- query problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads