On the complexity of data disjunctions.

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.