

Rarekh, Rajesh G., Nichitiu, Codrin and Honavar, Vasant G. (1997) A Polynomial Time Incremental Algorithm for Regular Grammar Inference. Technical Report TR9703, Department of Computer Science, Iowa State University.
Abstract
A Polynomial Time Incremental Algorithm for Regular Grammar Inference
Rajesh Parekh, Codrin Nichitiu, and Vasant Honavar
Artificial Intelligence Research Group
Department of Computer Science
226 Atanasoff Hall
Iowa State University
Ames, IA 50011. U.S.A.
parekh@cs.iastate.edu, codrin@enslyon.fr, honavar@cs.iastate.edu
Abstract
We present an efficient incremental algorithm for learning regular
grammars from labeled examples and membership queries. This algorithm is
an extension of Angluin's {\em ID} procedure to an incremental framework.
The learning algorithm is intermittently provided with labeled
examples and has access to a knowledgeable teacher capable of
answering membership queries. Based on the observed examples and
the teacher's responses to membership queries, the learner
constructs a deterministic finite automaton (DFA) with which
all examples observed thus far are consistent.
When additional examples are observed, the learner modifies this
DFA suitably to encompass the information provided by the new
examples. In the limit this algorithm is guaranteed to converge
to a minimum state DFA corresponding to the
target regular grammar. We prove the convergence of this algorithm
in the limit and analyze its time and space complexities.
Contact site administrator at: ssg@cs.iastate.edu
