On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals (1992)  (Make Corrections)  (95 citations)
Thomas Eiter, Georg Gottlob

  Home/Search   Context   Related

Links:   ACM   DBLP

 
View or download:
kr.tuwien.ac.at/staff/eite...aij2.ps.gz
Cached:  PS.gz  PS  PDF  Image  Update  Help

From:  kr.tuwien.ac.at/staff/eiter/18... (more)
(Enter author homepages)

Rate this article: (best)
  Comment on this article  
(Enter summary)

Abstract: We study the complexity of several recently proposed methods for updating or revising propositional knowledge bases under the principle of minimal change. In particular, we derive complexity results for the following problem: given a knowledge base T , an update p, and a formula q, decide whether q is derivable from T ffi p, the updated (or revised) knowledge base. Note that this problem includes the evaluation of the counterfactual p ? q over T , that is a conditional statement "if p,... (Update)

Cited by:   More
On Computing Belief Change Operations using - Quantified Boolean Formulas   (Correct)
A Consistency-Based Approach for Belief Change - James Delgrande School (2003)   (Correct)
Algorithms for Quantified Constraint Satisfaction Problems - Nikos Mamoulis Department (2004)   (Correct)

Similar documents (at the sentence level):
6.5%:   On the Complexity of Propositional Knowledge Base Revision.. - Eiter, Gottlob (1992)   (Correct)

Active bibliography (related documents):   More   All
0.7:   Propositional Circumscription and Extended Closed World.. - Eiter, Gottlob (1993)   (Correct)
0.6:   The Complexity of Logic-Based Abduction - Eiter, Gottlob (1993)   (Correct)
0.4:   The Complexity of Nested Counterfactuals and Iterated.. - Eiter, Gottlob (1993)   (Correct)

Similar documents based on text:   More   All
0.3:   Publication List 1998 - Informationssysteme, Wien (1998)   (Correct)
0.2:   Publication List 2000 - TU-Wien (2000)   (Correct)
0.2:   Le Mont-Saint-Michel, France, 1997. Also appeared in.. - Design Stanford Markus   (Correct)

Related documents from co-citation:   More   All
38:   Investigations into a theory of knowledge base revision: Preliminary report - Dalal - 1988
31:   Reasoning about action using a possible models approach (context) - Winslett - 1988
27:   the semantics of updates in databases (context) - Fagin, Ullman et al. - 1983

BibTeX entry:   (Update)

T. Eiter & G. Gottlob. On the complexity of propositional knowledge base revision, updates, and counterfactuals. Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 261-273, 1992. http://citeseer.ist.psu.edu/eiter92complexity.html   More

@inproceedings{ eiter92complexity,
    author = "Thomas Eiter and Georg Gottlob",
    title = "On the complexity of propositional knowledge base revision, updates, and counterfactuals",
    pages = "261--273",
    year = "1992",
    url = "citeseer.ist.psu.edu/eiter92complexity.html" }
Citations (may not include all citations):
3985   Computers and Intractability -- A Guide to the Theory of NP-.. (context) - Garey, Johnson - 1979
823   A Logic for Default Reasoning (context) - Reiter - 1980  ACM   DBLP
444   Circumscription -- A Form of Non-Monotonic Reasoning (context) - McCarthy - 1980
300   Semantical Considerations on Nonmonotonic Logics (context) - Moore - 1985
295   Applications of Circumscription to Formalizing Common-Sense .. - McCarthy - 1986  ACM   DBLP
284   On Closed-World Databases (context) - Reiter - 1978
199   the Difference between Updating a Knowledge Base and Revisin.. - Katsuno, Mendelzon - 1991
199   the Difference Between Updating a Knowledge Base and Revisin.. - Katsuno, Mendelzon - 1990
198   Reasoning about Action Using a Possible Models Approach (context) - Winslett - 1988  DBLP
187   Linear-time Algorithms for Testing the Satisfiability of Pro.. (context) - Dowling, Gallier - 1984
184   On Indefinite Data Bases and the Closed World Assumption (context) - Minker - 1982
158   Complexity Results for Nonmonotonic Logics (context) - Gottlob - 1992  DBLP
150   Propositional Knowledge Base Revision and Minimal Change (context) - Katsuno, Mendelzon - 1991  ACM   DBLP
148   The Complexity of Optimization Problems (context) - Krentel - 1988  ACM   DBLP
145   the Logic of Theory Change: Partial Meet Contraction and Rev.. (context) - Alchourr'on, Gardenfors et al. - 1985
142   Knowledge in Flux (context) - Gardenfors - 1988
118   Harvard University Press (context) - Lewis - 1973
115   Investigations into a Theory of Knowledge Base Revision: Pre.. - Dalal - 1988
113   Non-Monotonic Logic (context) - McDermott, Doyle - 1980
105   Bounded query classes (context) - Wagner - 1990  ACM   DBLP
100   Word Problems Requiring Exponential Time (context) - Stockmeyer, Meyer - 1973
96   the Relationship Between Circumscription and Negation as Fai.. (context) - Gelfond, Przymusinksa et al. - 1989
95   the Semantics of Updates in Databases (context) - Fagin, Ullman et al. - 1983
90   Propositional Circumscription and Extended Closed World Reas.. - Eiter, Gottlob - 1991
89   Artificial Intelligence (context) - Ginsberg - 1986  ACM   DBLP
72   Belief Revision and Default Reasoning: Syntax-Based Approach.. - Nebel - 1991  DBLP
69   Updating Logical Databases (context) - Winslett - 1990  ACM   DBLP
67   A Circumscriptive Theorem Prover - Ginsberg - 1989  ACM   DBLP
62   An Assumption-Based Truth Maintenance System (context) - de Kleer - 1986
60   Non-Monotonic Logic II: Nonmonotonic Modal Theories (context) - McDermott - 1982
59   Language Features for Flexible Handling of Exceptions in Inf.. - Borgida - 1985  ACM   DBLP
56   An Algorithm to Compute Circumscription (context) - Przymusinski - 1989  ACM   DBLP
56   A Knowledge Level Analysis of Belief Revision - Nebel - 1989  ACM
46   Updating Logical Databases (context) - Fagin, Kuper et al. - 1986  ACM   DBLP
44   Deduction in Non-Horn Databases (context) - Yahya, Henschen - 1985  DBLP
40   and Sparse Turing-Complete Sets for NP (context) - Kadin, NP et al. - 1989
38   And Some Facets of Complexity (context) - Papadimitriou, Yannakakis et al. - 1984
38   Introducing Actions into Qualitative Simulation - Forbus - 1989  DBLP
38   Updates and Counterfactuals - Grahne - 1991  DBLP
33   the Use of an Extended Relational Model to Handle Changing I.. (context) - Keller, Winslett-Wilkinson - 1985
30   A Unified View of Propositional Knowledge Base Updates (context) - Katsuno, Mendelzon - 1989  DBLP
29   Closed-World Databases and Circumscription (context) - Lifschitz - 1985  ACM   DBLP
29   Nonmonotonic Reasoning by Minimal Belief Revision (context) - Satoh - 1988  DBLP
26   Updating Propositional Formulas (context) - Weber - 1986  DBLP
24   Annals of Mathematics and Artificial Intelligence (context) - Marek, Truszczy'nsky et al. - 1990  ACM
24   Nonmonotonic Reasoning and the Closed World Assumption (context) - Bossu, Siegel - 1985
23   Negation as Failure: Careful Closure Procedure (context) - Gelfond, Przymusinska - 1986  ACM   DBLP
23   The Complexity of Closed World Reasoning and Circumscription (context) - Cadoli, Lenzerini - 1990  DBLP
14   Updates in Propositional Databases (context) - Dalal - 1988
13   Hypothetical Reasoning (context) - Rescher - 1964  ACM
10   The Coherence Theory of Truth (context) - Rescher - 1973
8   volume A of Handbook of Theoretical Computer Science (context) - Johnson, of et al. - 1990
5   New Developments in Structural Complexity Theory (context) - Hartmanis - 1990  ACM   DBLP
3   Introduction to Logical Programming (context) - Apt - 1987
3   LTUR: a simplified linear time unit resolution for Horn form.. (context) - Minoux - 1988
3   Complexity Classification in Truth Maintenance Systems (context) - Rutenburg - 1991
2   Higher Level Complexity Results for Abduction (context) - Eiter, Gottlob - 1992
2   Also Proceedings Workshop on Nonstandard Queries and Answers (context) - Grahne, Mendelzon et al. - 1991
1   Annals of Mathematics and Artificial Intelligence (context) - Winslett, for - 1991  ACM



The graph only includes citing articles where the year of publication is known.


Documents on the same site (http://www.kr.tuwien.ac.at/staff/eiter/1842-papers/):   More
Complexity Aspects of Various Semantics for Disjunctive Databases - Eiter, Gottlob (1993)   (Correct)
Semantics and Complexity of Abduction from Default Theories - Eiter, Gottlob, Leone (1997)   (Correct)
Default Logic as a Query Language - Cadoli, Eiter, Gottlob (1997)   (Correct)

Online articles have much greater impact   More about CiteSeer.IST   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST - Copyright Penn State and NEC