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 logic; default logic; abduction; intractability; tractability; circumscription; closed-world reasoning; non-monotonic inference tasks
68Q25: Analysis of algorithms and problem complexity
68T30: Knowledge representation
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68N17: Logic programming
Related Items
Graph theoretical structures in logic programs and default theories, Expressive power and complexity of partial models for disjunctive deductive databases, The complexity of propositional closed world reasoning and circumscription, Cumulative default logic: Finite characterization, algorithms, and complexity, The expressive powers of stable models for bound and unbound DATALOG queries, 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, On the computational complexity of assumption-based argumentation for default reasoning., Propositional default logics made easier: computational complexity of model checking., Default reasoning by deductive planning, A new methodology for query answering in default logics via structure-oriented theorem proving, 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
