## Polynomial time algorithm for constructing k-maintainable policies

### C. Baral and T. Eiter

## Abstract

In this paper we present a polynomial time algorithm for
constructing k-maintainable policies \cite{baral:maint00}. Our
algorithm, in polynomial time, constructs a $k$-maintainable
control policy, if one exists, or tells that no such policy is
possible. Our algorithm is based on SAT Solving, and employs a
suitable formulation of the existence of $k$-maintainable control
in a fragment of SAT which is tractable. We then give a logic
programming implementation of our algorithm and use it to give a
standard procedural algorithm. We then present several complexity
results about constructing $k$-maintainable controls, under
different assumptions such as $k=1$, and compact representation.