Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433870 | Theoretical Computer Science | 2016 | 27 Pages |
Abstract
In recent years different interesting subclasses of cfls have been found to be learnable by techniques generically called distributional learning. The theoretical study on the exact learning of cfls by those techniques under different learning schemes is now quite mature. On the other hand, positive results on the pac learnability of cfls are rather limited and quite weak. This paper shows that several subclasses of context-free languages that are known to be exactly learnable with positive data and membership queries by distributional learning techniques are pac learnable from positive data under some assumptions on the string distribution.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Chihiro Shibata, Ryo Yoshinaka,