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.