scientific article; zbMATH DE number 1962835

MaRDI QIDQ4418672zbMATH OpenFDO

Authors Arnaud Durand, Miki Hermann

Publication date 11 August 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2607/26070451.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in artificial intelligence (68T27)

Recommendations

• On compact representations of propositional circumscription
• On compact representations of propositional circumscription
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• The computational complexity of propositional cirquent calculus
• Completeness proofs for propositional logic with polynomial-time connectives
• On the counting complexity of propositional circumscription
• An exact algorithm for the constraint satisfaction problem: Application to logical inference
• A dichotomy in the complexity of propositional circumscription
• An approximative inference method for solving \(\exists \forall \)SO satisfiability problems
• The complexity of theorem proving in circumscription and minimal entailment

Cited in

(8)

• The complexity of model checking for circumscriptive formulae
• A dichotomy in the complexity of propositional circumscription
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• What makes propositional abduction tractable
• Monadic second-order model-checking on decomposable matroids
• The complexity of circumscriptive inference in Post's lattice
• Trichotomies in the complexity of minimal inference
• On the counting complexity of propositional circumscription

This page was built for publication:

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