Optimal regression for reasoning about knowledge and actions

H. Ditmarsch, van, Andreas Herzig, Tiago Lima, de

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

17 Citations (Scopus)


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 EXPTIMEcomplete when common knowledge is involved.
Original languageEnglish
Title of host publicationProceedings of the 22nd Conference on Artificial Intelligence (AAAI-07) 22-26 July 2007, Vancouver, British Columbia, Canada
Place of PublicationMenlo Park, California, USA
PublisherAAAI Press
ISBN (Print)978-1-577-35323-2
Publication statusPublished - 2007
Eventconference; AAAI-07, Vancouver, British Columbia, Canada; 2007-07-22; 2007-07-26 -
Duration: 22 Jul 200726 Jul 2007


Conferenceconference; AAAI-07, Vancouver, British Columbia, Canada; 2007-07-22; 2007-07-26
OtherAAAI-07, Vancouver, British Columbia, Canada

Cite this