Decidable Reasoning in a Modified Situation Calculus

Yilan Gu, Mikhail Soutchanski

We consider a modified version of the situation calculus built using a two-variable fragment of the first-order logic extended with counting quantifiers. We mention several additional groups of axioms that can be introduced to capture taxonomic reasoning. We show that the regression operator in this framework can be defined similarly to regression in the Reiter's version of the situation calculus. Using this new regression operator, we show that the projection and executability problems are decidable in the modified version even if an initial knowledge base is incomplete and open. For an incomplete knowledge base and for ontext-dependent actions, we consider a type of progression that is sound with respect to the classical progression. We show that the new knowledge base resulting after our progression is definable in our modified situation calculus if one allows actions with local effects only. We mention possible applications to formalization of Semantic Web services.

URL: http://www.cs.toronto.edu/~yilan/publications/papers/IJCAI-GuY1593.pdf