ITERATIVE AND RECURSIVE ALGORITHMS FOR TREE SEARCH AND PARTITION SEARCH OF THE LATTICE OF STRUCTURE MODELS

An important problem in reconstructability analysis, and modelling in general, is determination of the set of simplest models, all of which acceptably represent the information contained in a given overall system. Evaluation of these models depends on acceptability (semantic) criteria and structural criteria. Structural criteria determine whether one model is simpler than another. In this paper we assume the existence of acceptability criteria and mechanisms to determine if given models meet them. The general problem we solve is how to most efficiently generate the set of all models. We use these results to determine the set of simplest models that satisfy the acceptability criteria

The main results of the paper are: a procedural definition of a recursive Boolean lattice that is based on recursive partitioning of the set of models, a definition of a spanning tree of the lattice of models, and algorithms for non-duplicating generation and search of the lattice of models. The generation and search algorithms fall into two categories: (i) iterative and recursive algorithms that implement the definition of the spanning tree and use it to determine the set of simplest models; (ii) algorithms that implement recursive partition search of the lattice of models. Two algorithms for recursive partition search are given, one that applies the procedural definition of a recursive Boolean lattice to the full set of models, and one that first partitions the full set into C-Structure equivalence classes, and then applies the definition of the recursive Boolean lattice to the equivalence classes.