A polynomial time incremental algorithm for learning DFA

Rajesh Parekh, Codrin Nichitiu, Vasant Honavar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations


We present an efficient incremental algorithm for learning deterministic unite state automata (DFA) from labeled examples and membership queries. This algorithm is an extension of Angluin's 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. The learner constructs an initial hypothesis from the given set of labeled examples and the teacher's responses to membership queries. If an additional example observed by the learner is inconsistent with the current hypothesis then the hypothesis is modified minimally to make it consistent with the new example. The update procedure ensures that the modified hypothesis is consistent with all examples observed thus far. The algorithm is guaranteed to converge to a minimum state DFA corresponding to the target when the set of examples observed by the learner includes a live complete set. We prove the convergence of this algorithm and analyze its time and space complexities.

Original languageEnglish (US)
Title of host publicationGrammatical Inference - 4th International Colloquium, ICGI 1998, Proceedings
EditorsVasant Honavar, Giora Slutzki
PublisherSpringer Verlag
Number of pages13
ISBN (Print)3540647767, 9783540647768
StatePublished - 1998
Event4th International Colloquium on Grammatical Inference, ICGI 1998 - Ames, United States
Duration: Jul 12 1998Jul 14 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th International Colloquium on Grammatical Inference, ICGI 1998
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A polynomial time incremental algorithm for learning DFA'. Together they form a unique fingerprint.

Cite this