Optimal regression for reasoning about knowledge and actions

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

Optimal regression for reasoning about knowledge and actions

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 EXPTIMEcomplete when common knowledge is involved.

Original language	English
Title of host publication	Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07) 22-26 July 2007, Vancouver, British Columbia, Canada
Place of Publication	Menlo Park, California, USA
Publisher	AAAI Press
Pages	1070-1075
ISBN (Print)	978-1-577-35323-2
Publication status	Published - 2007
Externally published	Yes
Event	AAAI-07, Vancouver, British Columbia, Canada - Vancouver, Canada Duration: 22 Jul 2007 → 26 Jul 2007

Conference

Conference	AAAI-07, Vancouver, British Columbia, Canada
Country/Territory	Canada
City	Vancouver
Period	22/07/07 → 26/07/07

Cite this

@inproceedings{c03a3a7204604448958bc18408569aa7,

title = "Optimal regression for reasoning about knowledge and actions",

abstract = "We show how in the propositional case both Reiter{\textquoteright}s and Scherl & Levesque{\textquoteright}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{\textquoteright}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{\textquoteright} recent satisfiability-preserving reduction to our logic, we establish optimal decision procedures for both Reiter{\textquoteright}s and Scherl & Levesque{\textquoteright}s approaches: satisfiability is NP-complete for one agent, PSPACE-complete for multiple agents and EXPTIMEcomplete when common knowledge is involved.",

author = "{Ditmarsch, van}, H. and Andreas Herzig and {de Lima}, Tiago",

year = "2007",

language = "English",

isbn = "978-1-577-35323-2",

pages = "1070--1075",

booktitle = "Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07) 22-26 July 2007, Vancouver, British Columbia, Canada",

publisher = "AAAI Press",

note = "AAAI-07, Vancouver, British Columbia, Canada ; Conference date: 22-07-2007 Through 26-07-2007",

}

Optimal regression for reasoning about knowledge and actions. / Ditmarsch, van, H.; Herzig, Andreas; de Lima, Tiago.
Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07) 22-26 July 2007, Vancouver, British Columbia, Canada. Menlo Park, California, USA: AAAI Press, 2007. p. 1070-1075.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Optimal regression for reasoning about knowledge and actions

AU - Ditmarsch, van, H.

AU - Herzig, Andreas

AU - de Lima, Tiago

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 978-1-577-35323-2

SP - 1070

EP - 1075

BT - Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07) 22-26 July 2007, Vancouver, British Columbia, Canada

PB - AAAI Press

CY - Menlo Park, California, USA

T2 - AAAI-07, Vancouver, British Columbia, Canada

Y2 - 22 July 2007 through 26 July 2007

ER -

Optimal regression for reasoning about knowledge and actions

Abstract

Conference

Fingerprint

Cite this