On the Parameterised Complexity of Learning Patterns.
Computer and Information Sciences II - 26th International Symposium on Computer and Information Sciences, London, UK, 26-28 September 2011,
, pp.277-281
(2011), [peer-reviewed]
Event Date:
September 26-28, 2011
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…