Enumeration complexity of logical query problems with second-order variables

DOI10.4230/LIPICS.CSL.2011.189zbMATH Open1247.68073OpenAlexW2240520130MaRDI QIDQ2915682FDOQ2915682

Authors: Arnaud Durand, Yann Strozecki 

Publication date: 18 September 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_ee39.html

Recommendations

• Two-variable first order logic with counting quantifiers: complexity results
• Complexity Results for First-Order Two-Variable Logic with Counting
• Enumeration of monadic second-order queries on trees
• Enumeration complexity of conjunctive queries with functional dependencies
• Enumeration complexity of conjunctive queries with functional dependencies
• The Relational Polynomial-Time Hierarchy and Second-Order Logic
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• The complexity of first-order and monadic second-order logic revisited
• Complexity and expressive power of second-order extended Horn logic
• Second-order quantifier elimination. Foundations, computational aspects and applications

zbMATH Keywords

enumerationdescriptive complexityquery problem

Mathematics Subject Classification ID

Database theory (68P15) Descriptive complexity and finite models (68Q19) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (11)

• Enumerating models of DNF faster: breaking the dependency on the formula size
• Linear delay enumeration and monadic second-order logic
• Descriptive complexity for counting complexity classes
• A glimpse on constant delay enumeration (invited talk)
• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
• Enumeration complexity of poor man's propositional dependence logic
• Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
• Title not available (Why is that?)
• An Experimental Study of the Treewidth of Real-World Graph Data
• Enumeration complexity of conjunctive queries with functional dependencies
• On enumerating monomials and other combinatorial structures by polynomial interpolation

This page was built for publication: Enumeration complexity of logical query problems with second-order variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2915682)