Detecting sequential structure
Nevill-Manning, C.G. & Witten, I.H. (1995). Detecting sequential structure. In Proceedings of Workshop on Programming by Demonstration, Twelfth International Conference on Machine Learning, Lake Tahoe, USA, July 9th 1995 (pp. 49-56).
Permanent Research Commons link: https://hdl.handle.net/10289/4691
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 rules, and the detection of procedural substructure., Although SEQUITUR operates with abstract sequences, a number of concrete illustrations are provided.
This article has been published in Proceedings of Workshop on Programming by Demonstration, Twelfth International Conference on Machine Learning, Lake Tahoe, USA, July 9th 1995. © 1995 the authors.