1 Search Results for "de Lima, Tiago"

Document
DOI: 10.4230/DagSemProc.07351.15
Optimal Regression for Reasoning about Knowledge and Actions

Authors: Hans van Ditmarsch, Andreas Herzig, and Tiago de Lima

Published in: Dagstuhl Seminar Proceedings, Volume 7351, Formal Models of Belief Change in Rational Agents (2007)

Abstract
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.
Cite as

Hans van Ditmarsch, Andreas Herzig, and Tiago de Lima. Optimal Regression for Reasoning about Knowledge and Actions. In Formal Models of Belief Change in Rational Agents. Dagstuhl Seminar Proceedings, Volume 7351, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{vanditmarsch_et_al:DagSemProc.07351.15,
  author =	{van Ditmarsch, Hans and Herzig, Andreas and de Lima, Tiago},
  title =	{{Optimal Regression for Reasoning about Knowledge and Actions}},
  booktitle =	{Formal Models of Belief Change in Rational Agents},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7351},
  editor =	{Giacomo Bonanno and James Delgrande and J\'{e}r\^{o}me Lang and Hans Rott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07351.15},
  URN =		{urn:nbn:de:0030-drops-12077},
  doi =		{10.4230/DagSemProc.07351.15},
  annote =	{Keywords: Reasoning about action and change, reasoning about knowledge, situation calculus, frame problem, dynamic epistemic logic}
}
  • Refine by Author
  • 1 Herzig, Andreas
  • 1 de Lima, Tiago
  • 1 van Ditmarsch, Hans

  • Refine by Classification

  • Refine by Keyword
  • 1 Reasoning about action and change
  • 1 dynamic epistemic logic
  • 1 frame problem
  • 1 reasoning about knowledge
  • 1 situation calculus

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2007

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact