The problem of designing storage-efficient decision trees from decision tables is examined. It is shown that for most cases, the construction of the storage optimal decision tree is an NP-complete problem, and therefore a heuristic approach to the problem is necessary. A systematic procedure analogous to the information-theoretic heuristic is developed. The algorithm has low computational complexity and performs well experimentally.>

Graph theoretic properties of the PLA folding problem which not only give insight into the various folding problems but also provide efficient algorithms for solving the problems are presented. This work is based on the transformation of the PLA into graphs where cliques (completely connected subgraphs) in the graphs correspond to PLA folding sets. A simple heuristic technique known as the greedy algorithm can often identify near-maximum cliques in polynomial time. Experimental data show that this technique is extremely effective when applied to the graphs which generally arise in folding. Variations of the general folding problem such as bipartite folding and constrained folding are addressed.>