On Selection Functions that Do Not Preserve Normality
On Selection Functions that Do Not Preserve Normality
复制标题
关于不保持正态性的选择函数
DOI：
10.1007/978-3-540-45138-9_54
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Jan Reimann
中科院分区：
文献类型：
--
作者：
W. Merkle;Jan Reimann
所述序列选自序列R（0）R（1）.由语言L是所有比特R（n + 1）的子序列，使得前缀R（0）. R（n）在L中。根据Agafonoff [1]的一个结果，一个序列是正规的当且仅当一个正则语言选择的任何子序列再次是正规的。Kamae和韦斯[11]以及其他人提出了一个问题，即一种语言必须有多复杂，以至于根据这种语言进行选择并不能保持正常性。我们表明，有这样的语言，只是稍微复杂的比正规的，即，正常既不保持线性语言，也不确定性的一个计数器的语言。事实上，对于这两种类型的语言，都可以从正常序列中选择一个常量序列。
The sequence selected from a sequence R(0)R(1)... by a language L is the subsequence of all bits R(n + 1) such that the prefix R(0)...R(n) is in L. By a result of Agafonoff [1], a sequence is normal if and only if any subsequence selected by a regular language is again normal. Kamae and Weiss [11] and others have raised the question of how complex a language must be such that selecting according to the language does not preserve normality. We show that there are such languages that are only slightly more complicated than regular ones, namely, normality is neither preserved by linear languages nor by deterministic one-counter languages. In fact, for both types of languages it is possible to select a constant sequence from a normal one.