On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals.

@inproceedings{DBLP:conf/pods/EiterG92,
  author    = {Thomas Eiter and
               Georg Gottlob},
  title     = {On the Complexity of Propositional Knowledge Base Revision, Updates,
               and Counterfactuals},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {261-273},
  ee        = {http://doi.acm.org/10.1145/137097.137886, db/conf/pods/EiterG92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

Journal Edition

References

[1]

...

[2]

Anthony J. Bonner: A Logic for Hypothetical Reasoning. AAAI 1988: 480-484 BibTeX

[3]

Anthony J. Bonner: Hypothetical Datalog: Negation and Linear Recursion. PODS 1989: 286-300 BibTeX

[4]

Alexander Borgida: Language Features for Flexible Handling of Exceptions in Information Systems. ACM Trans. Database Syst. 10(4): 565-603(1985) BibTeX

[5]

...

[6]

Marco Cadoli, Maurizio Lenzerini: The Complexity of Closed World Reasoning and Circumscription. AAAI 1990: 550-555 BibTeX

[7]

Mukesh Dalal: Investigations into a Theory of Knowledge Base Revision. AAAI 1988: 475-479 BibTeX

[8]

...

[9]

...

[10]

William F. Dowling, Jean H. Gallier: Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae. J. Log. Program. 1(3): 267-284(1984) BibTeX

[11]

Thomas Eiter, Georg Gottlob: On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals. Artif. Intell. 57(2-3): 227-270(1992) BibTeX

[12]

Thomas Eiter, Georg Gottlob: Propositional Circumscription and Extended Closed-World Reasoning are IIp2-Complete. Theor. Comput. Sci. 114(2): 231-245(1993) BibTeX

[13]

...

[14]

...

[15]

Ronald Fagin, Jeffrey D. Ullman, Moshe Y. Vardi: On the Semantics of Updates in Databases. PODS 1983: 352-365 BibTeX

[16]

...

[17]

...

[18]

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX

[19]

Michael Gelfond, Halina Przymusinska, Teodor C. Przymusinski: On the Relationship Between Circumscription and Negation as Failure. Artif. Intell. 38(1): 75-94(1989) BibTeX

[20]

...

[21]

...

[22]

Matthew L. Ginsberg: A Circumscriptive Theorem Prover. Artif. Intell. 39(2): 209-230(1989) BibTeX

[23]

Georg Gottlob: Complexity Results for Nonmonotonic Logics. J. Log. Comput. 2(3): 397-425(1992) BibTeX

[24]

Gösta Grahne: Updates and Counterfactuals. KR 1991: 269-276 BibTeX

[25]

...

[26]

Juris Hartmanis: New Developments in Structural Complexity Theory. Theor. Comput. Sci. 71(1): 79-93(1990) BibTeX

[27]

...

[28]

Jim Kadin: P^(NP[O(log n)]) and Sparse Turing-Complete Sets for NP. J. Comput. Syst. Sci. 39(3): 282-298(1989) BibTeX

[29]

Hirofumi Katsuno, Alberto O. Mendelzon: On the Difference between Updating a Knowledge Base and Revising It. KR 1991: 387-394 BibTeX

[30]

Hirofumi Katsuno, Alberto O. Mendelzon: Propositional Knowledge Base Revision and Minimal Change. Artif. Intell. 52(3): 263-294(1992) BibTeX

[31]

Arthur M. Keller, Marianne Winslett: On the Use of an Extended Relational Model to Handle Changing Incomplete Information. IEEE Trans. Software Eng. 11(7): 620-633(1985) BibTeX

[32]

Mark W. Krentel: The Complexity of Optimization Problems. J. Comput. Syst. Sci. 36(3): 490-509(1988) BibTeX

[33]

...

[34]

...

[35]

...

[36]

...

[37]

Drew V. McDermott: Nonmonotonic Logic II: Nonmonotonic Modal Theories. J. ACM 29(1): 33-57(1982) BibTeX

[38]

...

[39]

Jack Minker: On Indefinite Databases and the Closed World Assumption. CADE 1982: 292-308 BibTeX

[40]

...

[41]

Bernhard Nebel: A Knowledge Level Analysis of Belief Revision. KR 1989: 301-311 BibTeX

[42]

Bernhard Nebel: Belief Revision and Default Reasoning: Syntax-Based Approaches. KR 1991: 417-428 BibTeX

[43]

Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity). J. Comput. Syst. Sci. 28(2): 244-259(1984) BibTeX

[44]

Teodor C. Przymusinski: An Algorithm to Compute Circumscription. Artif. Intell. 38(1): 49-73(1989) BibTeX

[45]

...

[46]

...

[47]

...

[48]

Vladislav Rutenburg: Complexity Classification of Truth Maintenance Systems. STACS 1991: 372-383 BibTeX

[49]

Ken Satoh: Nonmonotonic Reasoning by Minimal Belief Revision. FGCS 1988: 455-462 BibTeX

[50]

Andreas Weber: Updating Propositional Formulas. Expert Database Conf. 1986: 487-500 BibTeX

[51]

Marianne Winslett: Reasoning about Action Using a Possible Models Approach. AAAI 1988: 89-93 BibTeX

[52]

...

[53]

...

[54]

Adnan H. Yahya, Lawrence J. Henschen: Deduction in Non-Horn Databases. J. Autom. Reasoning 1(2): 141-160(1985) BibTeX

[55]

...

Referenced by

1. V. Wiktor Marek, Miroslaw Truszczynski: Revision Programming, Database Updates and Integrity Constraints. ICDT 1995: 368-382
2. Suryanarayana M. Sripada, Beat Wüthrich: Cumulative Updates. VLDB 1994: 534-545
3. Alberto O. Mendelzon, Tova Milo, Emmanuel Waller: Object Migration. PODS 1994: 232-242
4. Peter Z. Revesz: On the Semantics of Theory Change: Arbitration between Old and New Information. PODS 1993: 71-82
5. Gösta Grahne, Alberto O. Mendelzon, Peter Z. Revesz: Knowledgebase Transformations. PODS 1992: 246-260