MODELING SEQUENCES USING GRAMMARS AND AUTOMATA
Date
1994-02-01
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Keywords
Computer Science