  Constraints such as separation-of-duty are widely used to specify
requirements that supplement basic authorization policies. However, the
existence of constraints (and authorization policies) may mean that a user is
unable to fulfill her/his organizational duties because access to resources has
been denied. In short, there is a tension between the need to protect resources
(using policies and constraints) and the availability of resources. Recent work
on workflow satisfiability and resiliency in access control asks whether this
tension compromises the ability of an organization to achieve its objectives.
In this paper, we develop a new method of specifying constraints which subsumes
much related work and allows a wider range of constraints to be specified. The
use of such constraints leads naturally to a range of questions related to
"policy existence", where a positive answer means that an organization's
objectives can be realized. We analyze the complexity of these policy existence
questions and, for particular sub-classes of constraints defined by our
language, develop fixed-parameter tractable algorithms to solve them.
