PAC-Learning Unambiguous NTS Languages
PAC-Learning Unambiguous NTS Languages
复制标题
PAC-学习明确的 NTS 语言
DOI：
10.1007/11872436_6
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Alexander Clark
中科院分区：
文献类型：
--
作者：
Alexander Clark
非终结符分离语言（英语：Non-terminally Separated languages，NTS）是确定性上下文无关语言的一个子类，其中语言的子串和语法的非终结符之间存在稳定的关系。我们表明，当样本的分布是由PCFG生成的，基于与目标语言相同的语法，一类明确的NTS语言是PAC学习的正数据，与多项式的数据和计算的界限。
Non-terminally separated (NTS) languages are a subclass of deterministic context free languages where there is a stable relationship between the substrings of the language and the non-terminals of the grammar. We show that when the distribution of samples is generated by a PCFG, based on the same grammar as the target language, the class of unambiguous NTS languages is PAC-learnable from positive data alone, with polynomial bounds on data and computation.