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