A Polynomial Time Incremental Algorithm for Regular Grammar Inference







Deposit Papers 


Rarekh, Rajesh G., Nichitiu, Codrin and Honavar, Vasant G. (1997) A Polynomial Time Incremental Algorithm for Regular Grammar Inference. Technical Report TR97-03, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF


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.,,
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.

Subjects:All uncategorized technical reports
ID code:00000148
Deposited by:Staff Account on 17 January 1997

Contact site administrator at: