On the complexity of propositional knowledge base revision, updates, and counterfactuals

DOI10.1016/0004-3702(92)90018-SzbMath0763.68038WikidataQ59259776 ScholiaQ59259776MaRDI QIDQ1199919

Thomas Eiter, Georg Gottlob

Publication date: 17 January 1993

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

updating; counterfactual; minimal change; revising propositional knowledge bases

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T30: Knowledge representation

68T35: Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence

Related Items

On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision, Does This Set of Clauses Overlap with at Least One MUS?, Belief revision and update: Complexity of model checking, Belief revision within fragments of propositional logic, Capturing model-based ontology evolution at the instance level: the case of DL-Lite, Foundations of instance level updates in expressive description logics, AGM 25 years. Twenty-five years of research in belief change, First-order logical filtering, On the measure of conflicts: Shapley inconsistency values, Updating action domain descriptions, A syntax-based approach to measuring the degree of inconsistency for belief bases, Knowledgebase transformations, Logical representation and fusion of prioritized information based on guaranteed possibility measures: Application to the distance-based merging of classical bases, A consistency-based approach for belief change, Enhancing disjunctive logic programming systems by SAT checkers, Weakening conflicting information for iterated revision and knowledge integration, \(\text{DA}^2\) merging operators, Reasoning under inconsistency: a forgetting-based approach, Using local search to find MSSes and MUSes, Cumulative default logic: Finite characterization, algorithms, and complexity, A polynomial-time algorithm for reducing the number of variables in MAX SAT problem, Sound and efficient closed-world reasoning for planning, Reducing belief revision to circumscription (and vice versa), Semantics and complexity of abduction from default theories, Fast algorithms for revision of some special propositional knowledge bases, The complexity of belief update, Operational and complete approaches to belief revision, Default reasoning from conditional knowledge bases: Complexity and tractable cases, The complexity of theory revision, Minimal-change integrity maintenance using tuple deletions, Classical and weighted knowledgebase transformations, A logical framework for knowledge base maintenance, Propositional truth maintenance systems: Classification and complexity analysis, Propositional semantics for disjunctive logic programs, The sequence modeling method based on ECC in developing program specifications, The size of a revised knowledge base, Propositional belief base update and minimal change, Implementing semantic merging operators using binary decision diagrams, Local-search extraction of mUSes, Considerations on Belief Revision in an Action Theory, A FRAMEWORK FOR HANDLING LOGICAL INCONSISTENCIES IN THE FUSION OF BOOLEAN KNOWLEDGE BASES, MUST: Provide a Finer-Grained Explanation of Unsatisfiability, Distance-Based Semantics for C-Structure Belief Revision, A Default Logic Patch for Default Logic, Dealing Automatically with Exceptions by Introducing Specificity in ASP, Efficient Combination of Decision Procedures for MUS Computation, A practical parallel algorithm for propositional knowledge base revision

Uses Software

• Ltur

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• New developments in structural complexity theory
• Saturation, nonmonotonic reasoning and the closed-world assumption
• Semantical considerations on nonmonotonic logic
• The complexity of facets (and some facets of complexity)
• Closed-world databases and circumscription
• Negation as failure: careful closure procedure
• Reasoning about action. I: A possible worlds approach
• The complexity of optimization problems
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• On the relationship between circumscription and negation as failure
• An algorithm to compute circumscription
• A circumscriptive theorem prover
• A logic for default reasoning
• Circumscription - a form of non-monotonic reasoning
• Non-monotonic logic. I
• Propositional knowledge base revision and minimal change
• Modal logic for default reasoning
• Circumscriptive semantics for updating knowledge bases
• Deduction in non-Horn databases
• Updates and subjunctive queries
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Bounded Query Classes
• On the logic of theory change: Partial meet contraction and revision functions
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Nonmonotonic Logic II
• Complexity Results for Nonmonotonic Logics
• Counterfactuals