ML Anthology

Optimal Regression for Reasoning About Knowledge and Actions

Hans van Ditmarsch, Andreas Herzig, Tiago de Lima
AAAI 2007 pp. 1070-1076
doi:10.4230/dagsemproc.07351.15 /aaai/2007/vanditmarsch2007aaai-optimal/

Abstract

We show how in the propositional case both Reiter's and Scherl & Levesque's solutions to the frame problem can be modelled in dynamic epistemic logic (DEL), and provide an optimal regression algorithm for the latter. Our method is as follows: we extend Reiter's framework by integrating observation actions and modal operators of knowledge, and encode the resulting formalism in DEL with announcement and assignment operators. By extending Lutz' recent satisfiability-preserving reduction to our logic, we establish optimal decision procedures for both Reiter's and Scherl & Levesque's approaches: satisfiability is NP-complete for one agent, PSPACE-complete for multiple agents and EXPTIME-complete when common knowledge is involved.

PDF AAAI Semantic Scholar

Cite

Text

van Ditmarsch et al. "Optimal Regression for Reasoning About Knowledge and Actions." AAAI Conference on Artificial Intelligence, 2007. doi:10.4230/dagsemproc.07351.15

Markdown

[van Ditmarsch et al. "Optimal Regression for Reasoning About Knowledge and Actions." AAAI Conference on Artificial Intelligence, 2007.](https://mlanthology.org/aaai/2007/vanditmarsch2007aaai-optimal/) doi:10.4230/dagsemproc.07351.15

BibTeX

@inproceedings{vanditmarsch2007aaai-optimal,
  title     = {{Optimal Regression for Reasoning About Knowledge and Actions}},
  author    = {van Ditmarsch, Hans and Herzig, Andreas and de Lima, Tiago},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2007},
  pages     = {1070-1076},
  doi       = {10.4230/dagsemproc.07351.15},
  url       = {https://mlanthology.org/aaai/2007/vanditmarsch2007aaai-optimal/}
}