Reasoning about Policies Using Logic Programs

Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning

Volume

Papers from the 2001 AAAI Spring Symposium

Contents

We use a simplified version of the Policy Description Language PDL introduced in (Lobo, Bhatia, and 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 the stable model semantics of logic programs. We also identify a subclass of policies where the generation problem can be solved in polynomial time.