Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-1-4471-2155-8-35
Title: On the parameterised complexity of learning patterns
Authors: Stephan, F. 
Yoshinaka, R.
Zeugmann, T.
Issue Date: 2012
Citation: Stephan, F.,Yoshinaka, R.,Zeugmann, T. (2012). On the parameterised complexity of learning patterns. Computer and Information Sciences II - 26th International Symposium on Computer and Information Sciences, ISCIS 2011 : 277-281. ScholarBank@NUS Repository. https://doi.org/10.1007/978-1-4471-2155-8-35
Abstract: Angluin (1980) showed that there is a consistent and conservative learner for the class of non-erasing pattern languages; however, most of these learners are NP-hard. In the current work, the complexity of consistent polynomial time learners for the class of non-erasing pattern languages is revisited, with the goal to close one gap left by Angluin, namely the question on what happens if the learner is not required to output each time a consistent pattern of maximum possible length. It is shown that consistent learners are non-uniformly W[1]-hard inside the fixed-parameter hierarchy of Downey and Fellows (1999), and that there is also a W[1]-complete such learner. Only when one requires that the learner is in addition both, conservative and class-preserving, then one can show that the learning task is NP-hard for certain alphabet-sizes. © 2012 Springer-Verlag London Limited.
Source Title: Computer and Information Sciences II - 26th International Symposium on Computer and Information Sciences, ISCIS 2011
URI: http://scholarbank.nus.edu.sg/handle/10635/104602
DOI: 10.1007/978-1-4471-2155-8-35
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

8
checked on Nov 7, 2018

Page view(s)

40
checked on Nov 2, 2018

Google ScholarTM

Check

Altmetric


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