Answers are grounded in this paper and cite their sources.
Theoretical analysis demonstrates polynomial-time learning of regular sets using an interactive teacher, indicating that active queries enable efficient grammatical inference.
The problem of identifying an unknown regular set from examples of its members and nonmembers is addressed. It is assumed that the regular set is presented by a minimaMy adequate Teacher, which can answer membership queries about the set and can also test a conjecture and indicate whether it is equal to the unknown set and provide a counterexample if not. (A counterexample is a string in the symmetric difference of the correct set and the conjectured set.) A learning algorithm L * is described that correctly learns any regular set from any minimally adequate Teacher in time polynomial in the number of states of the minimum dfa for the set and the maximum length of any counterexample provided by the Teacher. It is shown that in a stochastic setting the ability of the Teacher to test conjectures may be replaced by a random sampling oracle, EX (). A polynomial-time learning algorithm is shown for a particular problem of context-free language identification. cl 1987 Academic Press, Inc. 1.
No takes yet. Share an insight, caveat, or question.
Dana Angluin (1987) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: