上下文无关语言上的递归函数——Ⅰ. CFPRF及CFRF的定义

• 作者: 董韫美
• 来源期刊: 中国科学E辑
• 学科: 数学
• 关键词: CFRF CFPRF 上下文无关语言的递归函数 CFL分层枚举 结构归纳法
• 年，卷（期）: 2002,（1）
• 页码范围: 103-115
• 页数: 13页
• 分类号: O1
• 字数: 10758字
• 语种: 中文
• DOI: 10.3321/j.issn:1006-9275.2002.01.014

摘要

建立上下文无关语言(CFL)上的递归函数理论. 在CFL上定义了函数类CFRF和它的真子类CFPRF,它们可用来十分直接地表述非数值加工算法. 事实上它们分别就是上下文无关语言上的偏递归函数和原始递归函数. 提出了证明CFPRF函数性质的结构归纳法,给出一种枚举CFL句子的方法,定义了极小算子. 基于CFL句子枚举,提出了极小算子的求值方法. 最后, 讨论了以CFRF为理论基础的可执行规约语言的设计和实现原则.

作者信息

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