A Polynomial Time Incremental Algorithm for Regular Grammar Inference

dc.contributor.author Parekh, Rajesh
dc.contributor.author Nichitiu, Codrin
dc.contributor.author Honavar, Vasant
dc.contributor.department Computer Science
dc.date 2018-02-13T23:07:32.000
dc.date.accessioned 2020-06-30T01:55:18Z
dc.date.available 2020-06-30T01:55:18Z
dc.date.issued 1997-01-17
dc.description.abstract <p>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.</p>
dc.identifier archive/lib.dr.iastate.edu/cs_techreports/141/
dc.identifier.articleid 1152
dc.identifier.contextkey 5396402
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath cs_techreports/141
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/19952
dc.source.bitstream archive/lib.dr.iastate.edu/cs_techreports/141/TR97_03.pdf|||Fri Jan 14 20:13:48 UTC 2022
dc.subject.disciplines Artificial Intelligence and Robotics
dc.subject.disciplines Theory and Algorithms
dc.subject.keywords grammar inference
dc.subject.keywords regular grammars
dc.subject.keywords finite state automata
dc.subject.keywords language learning
dc.subject.keywords active learning
dc.subject.keywords incremental algorithms
dc.subject.keywords machine learning
dc.title A Polynomial Time Incremental Algorithm for Regular Grammar Inference
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
File
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
TR97_03.pdf
Size:
197.74 KB
Format:
Adobe Portable Document Format
Description:
Collections