MODELING SEQUENCES USING GRAMMARS AND AUTOMATA
Craig G. Nevill-Manning, Ian H. Witten, David Maulsby · Libraries and Cultural Resources (University of Calgary) · 1994
Inference of structure from a sequence is useful for explanation, prediction, and compression. One technique described here infers a grammar from a sequence, and presents plausible explanations of how a sequence is structured. It has the added advantage of producing small explanations, and performs extremely well as a data compression technique. A second technique infers an automaton from a sequence, identifying branches, loops, recursive and non-recursive procedures. The two techniques have complementary strengths and weakness, and an inference problem which stymies each technique individually is shown to be amenable to a combination of the two.