中国科学E辑
中國科學E輯
중국과학E집
SCIENCE IN CHINA (SERIES E)
2002年
2期
254-273
,共20页
CFRF CFPRF 上下文无关语言的递归函数 受囿极值算子
CFRF CFPRF 上下文無關語言的遞歸函數 受囿極值算子
CFRF CFPRF 상하문무관어언적체귀함수 수유겁치산자
证明了函数类CFRF及其真子类CFPRF分别就是上下文无关语言(CFL)上的偏递归函数和原始递归函数. 讨论了它们与其他论域上定义的递归函数的关系,指出自然数上的函数和字上函数都是CFL上的函数. 给出了若干常用的字上原始递归函数,包括逻辑连接词和条件式,还给出构造原始递归函数用的强有力算子:受囿极大和受囿极小算子. 构造了两个非平凡的有重要用途的算法. 即任意CFL的特征函数,以及CFL句子的语法分解函数. 基于它们,叙述了扩展和限制函数论域的方法.
證明瞭函數類CFRF及其真子類CFPRF分彆就是上下文無關語言(CFL)上的偏遞歸函數和原始遞歸函數. 討論瞭它們與其他論域上定義的遞歸函數的關繫,指齣自然數上的函數和字上函數都是CFL上的函數. 給齣瞭若榦常用的字上原始遞歸函數,包括邏輯連接詞和條件式,還給齣構造原始遞歸函數用的彊有力算子:受囿極大和受囿極小算子. 構造瞭兩箇非平凡的有重要用途的算法. 即任意CFL的特徵函數,以及CFL句子的語法分解函數. 基于它們,敘述瞭擴展和限製函數論域的方法.
증명료함수류CFRF급기진자류CFPRF분별취시상하문무관어언(CFL)상적편체귀함수화원시체귀함수. 토론료타문여기타론역상정의적체귀함수적관계,지출자연수상적함수화자상함수도시CFL상적함수. 급출료약간상용적자상원시체귀함수,포괄라집련접사화조건식,환급출구조원시체귀함수용적강유력산자:수유겁대화수유겁소산자. 구조료량개비평범적유중요용도적산법. 즉임의CFL적특정함수,이급CFL구자적어법분해함수. 기우타문,서술료확전화한제함수론역적방법.
