Reasoning about Policies using Logic Programs

We use a simplified version of the Policy Description Language PDL introduced in (Lobo, Bhatis, & Naqvi 1999) to represent and reason about policies. In PDL a policy description is a collection of Event-Condition-Action-Rules that defines a mapping from event histories into action histories. In this paper we introduce the generation problem: finding an event history that generates a given action history, and state its complexity. Because of its high complexity we present a logic programming-based semantics for policies and encode a sound and complete solution of the generation problem using that stable model semantics of logic programs. We also identify a subclass of policies where the generation problem can be solved in polynomial time.