First-Order Strong Progression for Local-Effect Basic Action Theories (KR-2008)

First-Order Strong Progression for Local-Effect Basic Action Theories, Stavros Vassos, Gerhard Lakemeyer, and Hector Levesque, In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR-08), Sydney, Australia, 2008.
[pdf | citeulike | slides]

Abstract:
In a seminal paper Lin and Reiter introduced the notion of progression for basic action theories in the situation calculus. The idea is to replace an initial database by a new set of sentences which reflect the changes due to an action. Unfortunately, progression requires secondorder logic in general. In this paper, we introduce the notion of strong progression, a slight variant of Lin and Reiter that has the intended properties, and we show that in case actions have only local effects, progression is always first-order representable. Moreover, for a restricted class of local-effect axioms we show how to construct a new database that is finite.

Bibtex:

@inproceedings{vassos09localeffect,
address = {Sydney, Australia},
author = {Vassos, Stavros and Lakemeyer, Gerhard and Levesque, Hector},
booktitle = {Proceedings of 11th International Conference on Principles of Knowledge Representation and Reasoning (KR-08)},
editor = {Brewka, Gerhard and Lang, J{\’{e}}r{\^{o}}me},
pages = {662–672},
publisher = {AAAI Press},
title = {First-Order Strong Progression for Local-Effect Basic Action Theories},
year = {2009}
}