Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2006.07.044
Title: Learning a subclass of regular patterns in polynomial time
Authors: Case, J.
Jain, S. 
Reischuk, R.
Stephan, F. 
Zeugmann, T.
Keywords: Algorithmic learning
Average-case analysis
Pattern languages
Probabilistically exact learning
Issue Date: 2006
Source: Case, J., Jain, S., Reischuk, R., Stephan, F., Zeugmann, T. (2006). Learning a subclass of regular patterns in polynomial time. Theoretical Computer Science 364 (1) : 115-131. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2006.07.044
Abstract: An algorithm for learning a subclass of erasing regular pattern languages is presented. On extended regular pattern languages generated by patterns π of the form x 0 α 1 x 1 ... α m x m, where x 0, ..., x m are variables and α 1,..., α m strings of terminals of length c each, it runs with arbitrarily high probability of success using a number of examples polynomial in m (and exponential in c). It is assumed that m is unknown, but c is known and that samples are randomly drawn according to some distribution, for which we only require that it has certain natural and plausible properties. Aiming to improve this algorithm further we also explore computer simulations of a heuristic. © 2006 Elsevier B.V. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/43022
ISSN: 03043975
DOI: 10.1016/j.tcs.2006.07.044
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

2
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

2
checked on Nov 21, 2017

Page view(s)

45
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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