On the complexity of data disjunctions.

DOI10.1016/S0304-3975(01)00147-5zbMATH Open1061.68043MaRDI QIDQ1853503FDOQ1853503

Authors: Thomas Eiter, Helmut Veith 

Publication date: 21 January 2003

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

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

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)

Cites Work

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

Cited In (1)

• Inferring negative information from disjunctive databases

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)