On the parameterised complexity of learning patterns

Frank Stephan, Ryo Yoshinaka, Thomas Zeugmann

研究成果: 会議への寄与学会論文査読

8 被引用数 (Scopus)

抄録

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.

本文言語英語
ページ277-281
ページ数5
DOI
出版ステータス出版済み - 2012
イベント26th Annual International Symposium on Computer and Information Science, ISCIS 2011 - London, 英国
継続期間: 2011 9月 262011 9月 28

会議

会議26th Annual International Symposium on Computer and Information Science, ISCIS 2011
国/地域英国
CityLondon
Period11/9/2611/9/28

フィンガープリント

「On the parameterised complexity of learning patterns」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル