上下文无关语言上的递归函数--Ⅱ. CFPRF及CFRF定义的合宜性

• 作者: 董韫美
• 来源期刊: 中国科学E辑
• 学科: 工学
• 关键词: CFRF CFPRF 上下文无关语言的递归函数 受囿极值算子
• 年，卷（期）: 2002,（2）
• 页码范围: 254-273
• 页数: 20页
• 分类号: TP3
• 字数: 13735字
• 语种: 中文
• DOI: 10.3321/j.issn:1006-9275.2002.02.014

摘要

证明了函数类CFRF及其真子类CFPRF分别就是上下文无关语言(CFL)上的偏递归函数和原始递归函数. 讨论了它们与其他论域上定义的递归函数的关系,指出自然数上的函数和字上函数都是CFL上的函数. 给出了若干常用的字上原始递归函数,包括逻辑连接词和条件式,还给出构造原始递归函数用的强有力算子:受囿极大和受囿极小算子. 构造了两个非平凡的有重要用途的算法. 即任意CFL的特征函数,以及CFL句子的语法分解函数. 基于它们,叙述了扩展和限制函数论域的方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	董韫美	中国科学院软件研究所计算机科学开放研究实验室	9	59	6.0	7.0