In logic-based AI, formal reasoning about action has been a central topic. The main challenges have been the frame and the ramification problems. To solve them, there has been much work on causal action theories and several action languages for these theories have been proposed. We propose a new approach to characterize action languages in form of postulates. We first consider a language for writing causal action theories, and postulate several properties for the state transition models of these theories. We then consider their implementations in logic programs with answer set semantics. In particular, we propose to consider what we call permissible translations from these causal action theories to logic programs. First, for a small language, we use a computer program to systema...[ Read more ]

In logic-based AI, formal reasoning about action has been a central topic. The main challenges have been the frame and the ramification problems. To solve them, there has been much work on causal action theories and several action languages for these theories have been proposed. We propose a new approach to characterize action languages in form of postulates. We first consider a language for writing causal action theories, and postulate several properties for the state transition models of these theories. We then consider their implementations in logic programs with answer set semantics. In particular, we propose to consider what we call permissible translations from these causal action theories to logic programs. First, for a small language, we use a computer program to systematically examine all causal theories, and identify a minimal set of postulates that yields a unique permissible mapping under strong equivalence. We then prove that the result holds in the general case for any language as well.

This approach is quite general and can be used to evaluate and to compare action languages. And we use this approach to give characterizations of three representative action languages, B, C and BC, and to compare them based on our new characterization.