Raisonnement sur les actions : de Toronto à Amsterdam
Hans van Dimarsch, Andreas Herzig, Tiago de Lima · HAL (Le Centre pour la Communication Scientifique Directe) · 2007
We show how in the propositional case Reiter's well-known solution to the frame problem can be modelled in dynamic epistemic logic, and provide an optimal regression algorithm. Our method is as follows : we extend Reiter's solution by integrating observation actions and modal operators of knowledge, and encode the resulting formalism in a dynamic epistemic logic with announcement and assignment operators. By extending Lutz' recent satisfiability-preserving reduction for public announcement logic to assignments, we establish optimal complexity results for regression : satisfiability is NP-complete for one agent, PSPACE-complete for multiple agents and EXPTIME-complete when common knowledge is involved.