Inferring Sequential Structure
Craig G. Nevill-Manning · 1996
Abstract. Programming by demonstration requires detection and analysis of sequential patterns in a user’s input, and the synthesis of an appropriate structural model that can be used for prediction. This paper describes SEQUITUR, a scheme for inducing a structural description of a sequence from a single example. SEQUITUR integrates several different inference techniques: identification of lexical subsequences or vocabulary elements, hierarchical structuring of such subsequences, identification of elements that have equivalent usage patterns, inference of programming constructs such as looping and branching, generalisation by unifying grammar sequences, a number of concrete illustrations are provided. Key Words. PBD, sequence learning, grammatical inference Imperative programming involves the specification of a sequential series of elementary activities. Consequently, one might imagine programming-bydemonstration (PBD) to proceed by demonstrating a sequence of actions to an agent and having it pick up