Parse completion : a study of an inductive domain

Abstract: "Hierarchical knowledge structures are pervasive in Artificial Intelligence, yet very little is understood about how such structures may be effectively acquired. One way to represent the hierarchical component of knowledge structures is to use grammars. The grammar framework also provides a natural way to apply failure-driven learning to guide the induction of hierarchical knowledge structures. The conjunction of hierarchical knowledge structures and failure-driven learning defines a class of algorithms, which we call Parse Completion algorithms.This paper presents a theoretical explanation of this class that attepts to understand what makes this induction problem difficult, and to suggest where appropriate biases might lie to limit the search without overly restricting the richness of discoverable solutions. The explorations in this paper are not intended to produce a practical induction algorithm, although fruitful paths for such development are suggested."