On the complexity of data disjunctions.

DOI10.1016/S0304-3975(01)00147-5MaRDI QIDQ1853503zbMATH OpenFDO

Authors Thomas Eiter, Helmut Veith

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) Logic programming (68N17) Database theory (68P15)

Recommendations

• Theory and algorithms for disjunctive deductive databases
• On the complexity of discrete programming problems
• On the distributional complexity of disjointness
• scientific article; zbMATH DE number 177818
• The complexity of disjunction in intuitionistic logic
• The complexity of disjunction in intuitionistic logic
• On the complexity of some data analysis problems
• scientific article; zbMATH DE number 2227354
• The complexity of unions of disjoint sets
• The Complexity of Unions of Disjoint Sets

Cites work

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

Cited in

(1)

• Inferring negative information from disjunctive databases

Describes a project that uses

Uses Software

• Datalog

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

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