# A Polynomial Time Incremental Algorithm for Regular Grammar Inference

 Home  About  Browse  Search  Register  Subscriptions  Deposit Papers  Help

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: PostscriptAdobe PDF

## 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@ens-lyon.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
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