Academic
Publications
Distributional Learning of Some Context-Free Languages with a Minimally Adequate Teacher

Distributional Learning of Some Context-Free Languages with a Minimally Adequate Teacher,10.1007/978-3-642-15488-1_4,Alexander Clark

Distributional Learning of Some Context-Free Languages with a Minimally Adequate Teacher   (Citations: 5)
BibTex | RIS | RefWorks Download
Angluin showed that the class of regular languages could be learned from a Minimally Adequate Teacher (mat) providing membership and equivalence queries. Clark and Eyraud (2007) showed that some context free grammars can be identified in the limit from positive data alone by identifying the congruence classes of the language. In this paper we consider learnability of context free languages using a mat. We show that there is a natural class of context free languages, that includes the class of regular languages, that can be polynomially learned from a mat, using an algorithm that is an extension of Angluin’s lstar algorithm.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: