Accession Number:



Using First-Order Logic to Reason about Policies

Descriptive Note:

Journal Article

Corporate Author:

Cornell University Ithaca United States

Personal Author(s):

Report Date:


Pagination or Media Count:



A policy describes the conditions under which an action is permitted or forbidden. We show that a fragment of multi-sorted first-order logic can be used to represent and reason about policies. Because we use first-order logic, policies have a clear syntax and semantics. We show that further restricting the fragment results in a language that is still quite expressive yet is also tractable. More precisely, questions about entailment, such as May Alice access the file, can be answered in time that is a low-order polynomial indeed, almost linear in some cases, as can questions about the consistency of policy sets. We also give a brief overview of a prototype that we have built whose reasoning engine is based on the logic and whose interface is designed for non-logicians, allowing them to enter both policies and background information, such as Alice is a student, and to ask questions about the policies.

Subject Categories:

  • Computer Programming and Software

Distribution Statement: