The Inference Problem for Propositional Circumscription of Affine Formulas Is coNP-Complete.
Arnaud DurandMiki HermannPublished in: STACS (2003)
Keyphrases
- default logic
- conp complete
- np complete
- autoepistemic logic
- cnf formula
- disjunctive logic programming
- propositional logic
- belief base
- data exchange
- truth maintenance systems
- horn clauses
- propositional formulas
- decision problems
- bayesian networks
- nonmonotonic logics
- first order logic
- theorem prover
- logic programming
- nonmonotonic reasoning
- data complexity
- polynomial hierarchy
- loop formulas
- modal logic
- default theories
- logic programs
- inference rules
- conjunctive queries
- query answering
- incomplete information
- belief revision
- database