On the complexity of data disjunctions.

DOI10.1016/S0304-3975(01)00147-5zbMath1061.68043MaRDI QIDQ1853503

Helmut Veith, Thomas Eiter

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Computational complexityDeductive databasesComplexity upgradingConversion lemmaData disjunction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Logic programming (68N17)

Uses Software

• Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Languages represented by Boolean formulas
• Succinct circuit representations and leaf language classes are basically the same concept
• Computing functions with parallel queries to NP
• The complexity of optimization problems
• On truth-table reducibility to SAT
• Why not negation by fixpoint?
• A comparison of polynomial time reducibilities
• Succinct representation, leaf languages, and projection reductions
• Succinctness as a source of complexity in logical formalisms
• The complexity of propositional closed world reasoning and circumscription
• A taxonomy of complexity classes of functions
• Querying disjunctive databases through nonmonotonic logics
• Normal forms for second-order logic over finite structures, and classification of NP optimization problems
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Bounded Query Classes
• Computing protected circumscription
• The computational complexity of graph problems with succinct multigraph representation
• Relativization of questions about log space computability
• Autoepistemic logics as a unifying framework for the semantics of logic programs
• Relativized logspace and generalized quantifiers over finite ordered structures
• A note on succinct representations of graphs
• The complexity class θp2: Recent results and applications in AI and modal logic

This page was built for publication: On the complexity of data disjunctions.