Reasoning about actions and change in answer set programming

Abstract

This paper studies computational issues related to the problem of reasoning about actions and change (RAC) by exploiting its link with the Answer Set Programming paradigm. It investigates how increasing the expressiveness of a RAC formalism so that it can capture the three major problems of frame, ramification and qualification, affects its computational complexity, and how a solution to these problems can be implemented within Answer Set Programming. Our study is carried out within the particular language E. It establishes a link between language E and Answer Set Programming by presenting encodings of different versions of this language into logic programs under the answer set semantics. This provides a computational realization of solutions to problems related to reasoning about actions and change, that can make use of the recent development of effective systems for Answer Set Programming. © Springer-Verlag Berlin Heidelberg 2004.