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
1 - 1 of 1
No Thumbnail Available
- Name:
- TR97_03.pdf
- Size:
- 197.74 KB
- Format:
- Adobe Portable Document Format
- Description: