Optimal Regression for Reasoning about Knowledge and Actions

van Ditmarsch, Hans; Herzig, Andreas; de Lima, Tiago

doi:10.4230/DagSemProc.07351.15

Document

Optimal Regression for Reasoning about Knowledge and Actions

Authors Hans van Ditmarsch, Andreas Herzig, Tiago de Lima

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 7351
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2007-11-20

PDF

File

PDF

DagSemProc.07351.15.pdf

Filesize: 306 kB
22 pages

Document Identifiers

DOI: 10.4230/DagSemProc.07351.15
URN: urn:nbn:de:0030-drops-12077

Subject Classification

Keywords

Reasoning about action and change
reasoning about knowledge
situation calculus
frame problem
dynamic epistemic logic

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Hans van Ditmarsch, Andreas Herzig, and Tiago de Lima. Optimal Regression for Reasoning about Knowledge and Actions. In Formal Models of Belief Change in Rational Agents. Dagstuhl Seminar Proceedings, Volume 7351, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007) https://doi.org/10.4230/DagSemProc.07351.15

Author Details

Hans van Ditmarsch

Andreas Herzig

Tiago de Lima

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail