A survey of complexity results for non-monotonic logics
From MaRDI portal
Publication:4275256
DOI10.1016/0743-1066(93)90029-GzbMath0784.68039MaRDI QIDQ4275256
Publication date: 13 January 1994
Published in: The Journal of Logic Programming (Search for Journal in Brave)
autoepistemic logicdefault logicabductionintractabilitytractabilitycircumscriptionclosed-world reasoningnon-monotonic inference tasks
Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Logic programming (68N17)
Related Items (24)
The complexity of propositional closed world reasoning and circumscription ⋮ Cumulative default logic: Finite characterization, algorithms, and complexity ⋮ Default reasoning by deductive planning ⋮ A new methodology for query answering in default logics via structure-oriented theorem proving ⋮ The expressive powers of stable models for bound and unbound DATALOG queries ⋮ A Trajectory Calculus for Qualitative Spatial Reasoning Using Answer Set Programming ⋮ Propositional truth maintenance systems: Classification and complexity analysis ⋮ Complexity and undecidability results for logic programming ⋮ On the computational cost of disjunctive logic programming: Propositional case ⋮ Complexity of computing with extended propositional logic programs ⋮ Abduction from logic programs: Semantics and complexity ⋮ Is intractability of nonmonotonic reasoning a real drawback? ⋮ Sound and efficient closed-world reasoning for planning ⋮ Fixed-parameter tractability of disjunction-free default reasoning ⋮ Semantics and complexity of abduction from default theories ⋮ Weight constraint programs with evaluable functions ⋮ Proof complexity of propositional default logic ⋮ Graph theoretical structures in logic programs and default theories ⋮ Proof Complexity of Non-classical Logics ⋮ Expressive power and complexity of partial models for disjunctive deductive databases ⋮ Logic and Complexity in Cognitive Science ⋮ On the computational complexity of assumption-based argumentation for default reasoning. ⋮ Propositional default logics made easier: computational complexity of model checking. ⋮ Disjoint Logics
This page was built for publication: A survey of complexity results for non-monotonic logics
