2007/01/01 by Hans van Ditmarsch, van Ditmarsch, Hans, Andreas Herzig +3
Computer Science · #Advanced Algebra and Logic #Bayesian Modeling and Causal Inference #Logic, Reasoning, and Knowledge #Reasoning about action and change #dynamic epistemic logic #frame problem #reasoning about knowledge #situation calculus
paper · doi:10.4230/dagsemproc.07351.15
openalex publication_date 2007/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.