Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Context Free Language
Distributed Learning
Regular Language
Context Free Grammar
Subscribe
Academic
Publications
Distributional Learning of Some ContextFree Languages with a Minimally Adequate Teacher
Distributional Learning of Some ContextFree Languages with a Minimally Adequate Teacher,10.1007/9783642154881_4,Alexander Clark
Edit
Distributional Learning of Some ContextFree Languages with a Minimally Adequate Teacher
(
Citations: 5
)
BibTex

RIS

RefWorks
Download
Alexander Clark
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.
Conference:
International Colloquium on Grammatical Inference  ICGI
, pp. 2437, 2010
DOI:
10.1007/9783642154881_4
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(5)
...While those extensions take trees as input, a recent study shows that a rich subclass of contextfree languages can be learnt from string data by using an observation table [
15
]...
Ryo Yoshinaka
.
PolynomialTime Identification of Multiple ContextFree Languages from...
...Let us now move onto the theory of context free grammatical inference, in particular the theory of congruence based approaches as explored in [10, 11, 6,
12
]...
...The most basic of these models, presented in [
12
] makes the representational assumption that the nonterminals of the gramar generate congruence classes of the language...
...In [
12
], a similar algorithm was shown to polynomially learn the class of congruential CFGs from a minimally adequate teacher (mat)...
...[
12
]) we can get a result under the mat model...
Alexander Clark
.
Towards General Algorithms for Grammatical Inference
...Given a richer source of data, including membership queries, it is possible to increase the class of languages learned, while maintaining this basic representational assumption (see [
5
] in this volume)...
Alexander Clark
.
Learning Context Free Grammars with the Syntactic Concept Lattice
...The primal approach is taken in [
4
, 8, 13, 14, 15, 16] and the dual approach is taken in [12,2,5,7]...
...Among those, let us compare the learning of congruential cfgs by Clark [
4
] and that of cdeterministic cfgs by Shirakawa and Yokomori [12] as examples of those two approaches...
Ryo Yoshinaka
,
et al.
Towards Dual Approaches for Learning ContextFree Grammars Based on Sy...
...For example, one can reasonably define congruential acgs and give a learning algorithm for them under the same learning scheme as in the preceding work [
18
, 4]...
Ryo Yoshinaka
,
et al.
Distributional Learning of Abstract Categorial Grammars
References
(19)
Polynomial Identification in the Limit of Substitutable Contextfree Languages
(
Citations: 17
)
Alexander Clark
,
Remi Eyraud
Journal:
Journal of Machine Learning Research  JMLR
, 2007
Inference of Reversible Languages
(
Citations: 279
)
Dana Angluin
Journal:
Journal of The ACM  JACM
, vol. 29, no. 3, pp. 741765, 1982
Learning Regular Sets from Queries and Counterexamples
(
Citations: 657
)
Dana Angluin
Journal:
Information and Computation/information and Control  IANDC
, vol. 75, no. 2, pp. 87106, 1987
A Polynomial Algorithm for the Inference of Context Free Languages
(
Citations: 11
)
Alexander Clark
,
Rémi Eyraud
,
Amaury Habrard
Conference:
International Colloquium on Grammatical Inference  ICGI
, pp. 2942, 2008
Polynomialtime MAT learning of cdeterministic contextfree grammars
(
Citations: 7
)
H. Shirakawa
,
T. Yokomori
Published in 1993.
Sort by:
Citations
(5)
PolynomialTime Identification of Multiple ContextFree Languages from Positive Data and Membership Queries
(
Citations: 3
)
Ryo Yoshinaka
Conference:
International Colloquium on Grammatical Inference  ICGI
, pp. 230244, 2010
Towards General Algorithms for Grammatical Inference
(
Citations: 2
)
Alexander Clark
Conference:
Algorithmic Learning Theory  ALT
, pp. 1130, 2010
Learning Context Free Grammars with the Syntactic Concept Lattice
(
Citations: 2
)
Alexander Clark
Conference:
International Colloquium on Grammatical Inference  ICGI
, pp. 3851, 2010
Towards Dual Approaches for Learning ContextFree Grammars Based on Syntactic Concept Lattices
Ryo Yoshinaka
,
ERATO MINATO
Distributional Learning of Abstract Categorial Grammars
Ryo Yoshinaka
,
Makoto Kanazawa