2026-07-22T08:35:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1207 2024-03-06T11:07:41Z ddc:004 open_access

Optimal Regression for Reasoning about Knowledge and Actions van Ditmarsch, Hans Herzig, Andreas de Lima, Tiago Reasoning about action and change reasoning about knowledge situation calculus frame problem dynamic epistemic logic 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans van Ditmarsch and Andreas Herzig and Tiago de Lima 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 7351, Formal Models of Belief Change in Rational Agents (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07351.15 urn:nbn:de:0030-drops-12077 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07351.15 eng https://creativecommons.org/licenses/by/4.0/legalcode