The Complexity of Belief Update

Liberatore, Paolo

The Complexity of Belief Update

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 68-72.

Abstract

Belief revision and belief update are two different forms of belief change, and they serve different purposes. In this paper we focus on belief update, the formalization of change in beliefs due to changes in the world. The complexity of the basic update (introduced by Winslett [1990]) has been determined in [Eiter and Gottlob, 1992). Since then, many other formalizations have been proposed to overcome the limitations and drawbacks of Winslett's update. In this paper we analyze the complexity of the proposals presented in the literature, and relate some of them to previous work on closed world reasoning.

Paolo Liberatore. 1997. The Complexity of Belief Update. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97. IJCAI, 68–72. https://ijcai.org/proceedings/1997/11

@inproceedings{ijcai1997p11,
  title     = {The Complexity of Belief Update},
  author    = {Liberatore, Paolo},
  booktitle = {Proceedings of the Fifteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-97}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Martha E. Pollack},
  pages     = {68--72},
  year      = {1997},
  note      = {Automated Reasoning},
  url       = {https://ijcai.org/proceedings/1997/11},
}

TY  - CPAPER
TI  - The Complexity of Belief Update
AU  - Liberatore, Paolo
T2  - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1997
SP  - 68
EP  - 72
UR  - https://ijcai.org/proceedings/1997/11
ER  -