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

作　　者：董韫美[1] 

机构地区：[1]中国科学院软件研究所计算机科学开放研究实验室,北京100080

出　　处：《中国科学（E辑）》2002年第2期254-273,共20页Science in China(Series E)

基　　金：国家自然科学基金资助项目(批准号:69873042)

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

关 键 词：合宜性 CFRF CFPRF 上下文无关语言 递归函数 受囿极值算子 特征函数 语法分解函数 

分 类 号：O141.4[理学—数学]