Handling Termination in a Logical Language for Active Rules

Statelog is a Datalog extension integrating the declarative semantics of deductive rules with the possibility to define updates in the style of active and production rules. The language is surprisingly simple, yet captures many essential features of active rules. After reviewing the basics of active rules, production rules, and deductive rules, we elaborate on the problem of handling rule termination in the context of Statelog: It is undecidable whether a Statelog program terminates for all databases, and PSPACE-complete for a given database. The latter can be accomplished within the logical language: for every Statelog program P, there is a terminating program P^↓ which decides for any given database 𝒟, whether P ∪ 𝒟 terminates.