Learning Finite-State Machines from Inexperienced Teachers

TitleLearning Finite-State Machines from Inexperienced Teachers
Publication TypeConference Paper
Year of Publication2006
AuthorsGrinchtein, O, Leucker, M
Conference NameGrammatical Inference: Algorithms and Applications, 8th International Colloquium, {ICGI 2006}
SeriesLecture Notes in Computer Science
Volume4201
Abstract

A popular learning algorithm is Angluin's L* algorithm in which a minimal deterministic finite automaton for a regular language is learned based on so-called membership and equivalence queries addressed to a teacher and an oracle, respectively. In this setting, a teacher will answer queries either positively or negatively. In many application scenarios, however, parts of the machine to learn are not completely specified or not observable. Then, queries may be answered inconclusively. In this paper, we study learning algorithms which are designed to work with such an inexperienced teacher.

URLhttp://dx.doi.org/10.1007/11872436_30
Bibtex: 
@inproceedings {GrinchteinL06b,
	title = {Learning Finite-State Machines from Inexperienced Teachers},
	booktitle = {Grammatical Inference: Algorithms and Applications, 8th International Colloquium, {ICGI 2006}},
	series = {Lecture Notes in Computer Science},
	volume = {4201},
	year = {2006},
	abstract = {A popular learning algorithm is Angluin{\textquoteright}s L* algorithm in which a minimal deterministic finite automaton for a regular language is learned based on so-called membership and equivalence queries addressed to a teacher and an oracle, respectively. In this setting, a teacher will answer queries either positively or negatively. In many application scenarios, however, parts of the machine to learn are not completely specified or not observable. Then, queries may be answered inconclusively. In this paper, we study learning algorithms which are designed to work with such an inexperienced teacher.},
	url = {http://dx.doi.org/10.1007/11872436_30},
	author = {Olga Grinchtein and Martin Leucker}
}
Postscript: