Identification of unions of languages drawn from an identifiable class
Identification of unions of languages drawn from an identifiable class
复制标题
识别来自可识别类的语言联合
DOI：
10.5555/93335.93373
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
Keith Wright
中科院分区：
文献类型：
--
作者：
Keith Wright
我们遵循黄金开始的一系列研究，并由盎格鲁因继续。黄金定义了语言类的属性：从积极示例（即文本）中限制的可识别性。这意味着，给定从类中某些语言绘制的任何示例流都可以产生一系列猜测，从而收敛到绘制示例的语言。假设我们为我们提供了一类可以从文本中识别的语言，以及从其中两种语言中绘制的示例流。是否可以将限制融合到一起解释示例的两种语言？答案是：通常，不。我们定义语言类的属性，以确保这种双语标识是可能的。我们称这种语言类的属性有限弹性。有限弹性可以通过采用一对语言的操作来保存。这概括了由于Shinohara引起的结果。 Shinohara表明，对文本的模式语言是可以识别的。很容易看出，模式语言类具有有限的弹性。现在，我们看到Shinohara的结果符合任何具有有限弹性的语言课程。
We follow a line of research begun by Gold and continued by Angluin. Gold defined a property of language classes: identifiability in the limit from positive examples (i.e. text). This means that given any stream of examples drawn from some language in the class it is possible to produce a stream of guesses that converges to the language from which the examples are drawn. Suppose we are given a class of languages that is identifiable from text, and a stream of examples drawn from two of those languages intermixed. Is it possible to converge in the limit to a pair of languages that together explain the examples? The answer is: in general, no. We define a property of language classes that ensures such bilingual identification is possible. We call this property of language classes finite elasticity. Finite elasticity is preserved by the operation of taking unions of pairs of languages. This generalizes a result due to Shinohara. Shinohara has shown that pairs of pattern languages are identifiable from text. It is easy to see that the class of pattern languages has finite elasticity. We now see that Shinohara's result holds for any language class with finite elasticity.