Reasoning about Policies Using Logic Programs

Tran Cao Son and Jorge Lobo

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.