On the complexity of propositional knowledge base revision, updates, and counterfactuals
From MaRDI portal
Publication:1199919
DOI10.1016/0004-3702(92)90018-SzbMath0763.68038WikidataQ59259776 ScholiaQ59259776MaRDI QIDQ1199919
Publication date: 17 January 1993
Published in: Artificial Intelligence (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35)
Related Items
DL-Lite Ontology Revision Based on An Alternative Semantic Characterization, Belief Merging by Examples, Cumulative default logic: Finite characterization, algorithms, and complexity, Considerations on Belief Revision in an Action Theory, Belief Update Within Propositional Fragments, The complexity class θp2: Recent results and applications in AI and modal logic, A logical framework for knowledge base maintenance, Implementing semantic merging operators using binary decision diagrams, Local-search extraction of mUSes, A polynomial-time algorithm for reducing the number of variables in MAX SAT problem, Propositional truth maintenance systems: Classification and complexity analysis, Propositional semantics for disjunctive logic programs, Belief revision within fragments of propositional logic, Unnamed Item, Capturing model-based ontology evolution at the instance level: the case of DL-Lite, A general framework for computing maximal contractions, A FRAMEWORK FOR HANDLING LOGICAL INCONSISTENCIES IN THE FUSION OF BOOLEAN KNOWLEDGE BASES, A theory of change for prioritised resilient and evolvable software systems, On the measure of conflicts: Shapley inconsistency values, Updating action domain descriptions, Sound and efficient closed-world reasoning for planning, Mixed Iterated Revisions: Rationale, Algorithms, and Complexity, Fixpoint semantics for active integrity constraints, Reducing belief revision to circumscription (and vice versa), Semantics and complexity of abduction from default theories, Foundations of instance level updates in expressive description logics, On getting rid of the preprocessing minimization step in MUC-finding algorithms, MUST: Provide a Finer-Grained Explanation of Unsatisfiability, Fast algorithms for revision of some special propositional knowledge bases, A syntax-based approach to measuring the degree of inconsistency for belief bases, Computational approaches to finding and measuring inconsistency in arbitrary knowledge bases, The sequence modeling method based on ECC in developing program specifications, An extension-based approach to belief revision in abstract argumentation, The size of a revised knowledge base, Propositional belief base update and minimal change, Knowledgebase transformations, Prioritized assertional-based removed sets revision of \textit{DL}-\textit{Lite} belief bases, AGM 25 years. Twenty-five years of research in belief change, First-order logical filtering, Belief revision and update: Complexity of model checking, Unnamed Item, Minimal-change integrity maintenance using tuple deletions, Does This Set of Clauses Overlap with at Least One MUS?, Active integrity constraints for general-purpose knowledge bases, Reasoning under inconsistency: a forgetting-based approach, Belief revision in Horn theories, On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision, Distance-Based Semantics for C-Structure Belief Revision, A Default Logic Patch for Default Logic, Dealing Automatically with Exceptions by Introducing Specificity in ASP, Classical and weighted knowledgebase transformations, GenB: A General Solver for AGM Revision, Instance-Level Update in DL-Lite Ontologies through First-Order Rewriting, On the complexity of inconsistency measurement, Efficient Combination of Decision Procedures for MUS Computation, The complexity of belief update, Using local search to find MSSes and MUSes, Operational and complete approaches to belief revision, Default reasoning from conditional knowledge bases: Complexity and tractable cases, A practical parallel algorithm for propositional knowledge base revision, The complexity of theory revision, Approaches to measuring inconsistency for stratified knowledge bases, 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
Uses Software
Cites Work
- \(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
- 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
