Knowledge updates: Semantics and complexity issues

Chitta Baral, Yan Zhang

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


We consider the problem of updating of an agent's knowledge. We propose a formal method of knowledge update on the basis of the semantics of modal logic S5. In our method, an update is specified according to the minimal change on both the agent's actual world and knowledge. We discuss general minimal change properties of knowledge update and show that our knowledge update operator satisfies all the update postulates of Katsuno and Mendelzon. We characterize several specific forms of knowledge update which have important applications in reasoning about change of agents' knowledge. We also examine the persistence property of knowledge and ignorance associated with knowledge update. We then investigate the computational complexity of model checking for knowledge update. We first show that in general the model checking for knowledge update is Σ2P-complete. We then identify a subclass of knowledge update problems that has polynomial time complexity for model checking. We point out that some important knowledge update problems belong to this subclass. We further address another interesting subclass of knowledge update problems for which the complexity of model checking is NP-complete.

Original languageEnglish (US)
Pages (from-to)209-243
Number of pages35
JournalArtificial Intelligence
Issue number1-2
StatePublished - May 2005


  • Belief revision and update
  • Complexity
  • Knowledge representation
  • Knowledge update
  • Kripke structures
  • S5 modal logic

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'Knowledge updates: Semantics and complexity issues'. Together they form a unique fingerprint.

Cite this