Decidable Reasoning About Time in Finite-Domain Situation Calculus Theories

The plan existence problem asks, given a goal in the form of a formula in modal logic, an initial epistemic state (a pointed Kripke model), and a set of epistemic actions, whether there exists a sequence of actions that can be applied to reach the goal. We prove that even in the case where the preconditions of the epistemic actions have modal depth at most 1, and there are no postconditions, the plan existence problem is undecidable. The (un)decidability of this problem was previously unknown.

Decidability or complexity issues about the consistency problem for description logics with concrete domains have already been analysed with tableaux-based or type elimination methods. Concrete domains in ontologies are essential to consider concrete objects and predefined relations. In this work, we expose an automata-based approach leading to the optimal upper bound EXPTIME, that is designed by enriching the transitions with symbolic constraints. We show that the nonemptiness problem for such automata belongs to EXPTIME if the concrete domains satisfy a few simple properties. Then, we provide a reduction from the consistency problem for ontologies, yielding EXPTIME-membership. Thanks to the expressivity of constraint automata, the results are extended to additional ingredients such as inverse roles, functional role names and constraint assertions, while maintaining EXPTIME-membership, which illustrates the robustness of the approach

This paper proposes a Situation Calculus solution to the frame problem for obligation-producing actions, which are actions that create obligations on the part of the agent that performs them. As an example of such actions, we have an opening door action performed by an agent, which has the subsequent obligation of getting the door closed. Demolombe and others extend Raymond Reiter's solution to the frame problem for ordinary actions to accommodate obligation-producing actions. Obligation-producing actions do affect the truth value of a newly introduced fluent that captures the accessibility relation used in semantics of obligation modalities in the Situation Calculus. Our work simplifies Demolombe's characterization of the accessibility relation by eliminating the notion of ideality of situations, thereby remaining close to Kripke-style possible-world semantics for deontic logic, in the spirit of Governatori's approach. Furthermore, we spell out details of a complete solution by extending basic action theories of Reiter to the new setting. Finally, we extend Reiter's regression operator for reasoning about actions back to the initial situation to this new setting. Our solution yields intuitive properties that one would expect from obligations: for example, if a sentence is obligatory to an agent in a given situation, it remains so in subsequent situations unless the obligation is explicitly stopped.