Optimal Regression for Reasoning about Knowledge and Actions

Hans van Ditmarsch, Andreas Herzig, Tiago de Lima

We show how in the propositional case both Reiter's and Scherl and 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 amd Levesque's approaches: satisfiability is NP-complete for one agent, PSPACE-complete for multiple agents and EXPTIME-complete when common knowledge is involved.

Subjects: 11. Knowledge Representation; 3. Automated Reasoning

Submitted: Apr 24, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.