Efficiently Inducing Determinations: A Complete and Systematic Search Algorithm That Uses Optimal Pruning

Abstract

Determinations are a useful type of functional knowledge representation. Applications include knowledge-based systems, analogical reasoning, database design, and robotic sensing systems. This paper presents an efficient, batch algorithm for inducing all minimal determinations from observed data. The algorithm is based on breadth-first search and runs in polynomial time and space given a user-supplied parameter limiting the maximum size of a determination. The algorithm uses probabilistic measures to induce determinations despite noisy data. One key contribution is the identification of an enumeration order in the space of possible determinations that affords a complete and systematic search. Another contribution lists axioms that relate neighboring states and allow the construction of pruning rules. A third contribution formulates a perfect hash function for states in this space and facilitates optimal use of the pruning rules. This paper also sketches an algorithm that can incrementally revise a set of determinations given additional data.