Optimal regression for reasoning about knowledge and actions

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

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


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
Externally publishedYes
EventAAAI-07, Vancouver, British Columbia, Canada - Vancouver, Canada
Duration: 22 Jul 200726 Jul 2007


ConferenceAAAI-07, Vancouver, British Columbia, Canada


Dive into the research topics of 'Optimal regression for reasoning about knowledge and actions'. Together they form a unique fingerprint.

Cite this