An Algorithm for Optimal PLA Folding

Abstract

In this paper we present a graph-theoretic formulation of the optimal PLA folding problem. The class of admissible PLA foldings is defined. Necessary and sufficient conditions for obtaining the optimal folding are given. A subproblem of the optimal problem is shown to be NP-complete, and a heuristic algorithm is given which has proven to be effective on a number of test problems.