2026-07-22T18:09:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3231 2024-03-06T10:33:59Z ddc:004 open_access

Enumeration Complexity of Logical Query Problems with Second-order Variables Durand, Arnaud Strozecki, Yann descriptive complexity enumeration query problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnaud Durand and Yann Strozecki 2011 Is Part Of LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2011.189 urn:nbn:de:0030-drops-32313 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.189 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode