Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ic.2012.07.001
Title: Automatic learning of subclasses of pattern languages
Authors: Case, J.
Jain, S. 
Le, T.D.
Ong, Y.S.
Semukhin, P.
Stephan, F. 
Issue Date: 2012
Source: Case, J., Jain, S., Le, T.D., Ong, Y.S., Semukhin, P., Stephan, F. (2012). Automatic learning of subclasses of pattern languages. Information and Computation 218 : 17-35. ScholarBank@NUS Repository. https://doi.org/10.1016/j.ic.2012.07.001
Abstract: Automatic classes are classes of languages for which a finite automaton can decide the membership problem for the languages in the class, in a uniform way, given an index for the language. For alphabet size of at least 4, every automatic class of erasing pattern languages is contained, for some constant n, in the class of all languages generated by patterns which contain (1) every variable only once and (2) at most n symbols after the first occurrence of a variable. It is shown that such a class is automatically learnable using a learner with the length of the long-term memory being bounded by the length of the first example seen. The study is extended to show the learnability of related classes such as the class of unions of two pattern languages of the above type. © 2012 Elsevier Inc.
Source Title: Information and Computation
URI: http://scholarbank.nus.edu.sg/handle/10635/43096
ISSN: 08905401
DOI: 10.1016/j.ic.2012.07.001
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

5
checked on Apr 2, 2018

WEB OF SCIENCETM
Citations

3
checked on Apr 2, 2018

Page view(s)

61
checked on Apr 21, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.