• 中国科学院院士
董韫美
董韫美_期刊论文_中国工程院院士馆
期刊论文
多类型递归函数
2015年 -董韫美-《中国科学:数学》
摘要:本文旨在建立多类型递归函数(MTRF),目的是,为在计算机上实现的函数式语言提供理论原型.MTRF函数是可计算函数,其定义域和值域的数据类型包括:自然数、逻辑值、有穷字母表上的字、上下文无关语言(CFL)句子、CFL句子的分析树.本文指出MTRF函数与自然数递归函数是等价的,构造了可在计算机上实现的MTRF函数eval,可用来对任意MTRF函数求值.
CFL句子计数和分层词典序枚举
2006年 -董韫美-《中国科学E辑:信息科学》
摘要:通过按推导树高度对句子分层,建立了句子集合中的分层词典序,进而发展出一种基于文法的,依分层词典序的,CFL句子计数和枚举方法,获得句子枚举的多个高效算法,对于无二义CFG,首先提出一个基础算法N2L,时间复杂度为O(n·lg(n)),n是被枚举句子的长度.对N2L进行改造,得到两个算法TD和BU,时间复杂度均为O(n).对任意CFG,利用其推导树文法为工具后,文法无二义的限制被去除.对于一般的CFG,不论是否二义文法,也得到了依分层词典序的,时间复杂度为O(n)的枚举算法,同时枚举出句子及其推导树.该文的结果,从正面圆满回答了D(?)m(?)si提出的未决问题,即是否有按词典序,时间复杂度为O(n)的枚举算法?以及是否时间复杂度仅依赖于文法结构,及被枚举字之前同样长度的字的个数?本文给出的解答甚至比原问题所期望的更好.
中国科学院计算机科学重点实验室
2003年 -董韫美-《中国基础科学》
一个支持规约获取的形式规约语言
2002年 -董韫美-《计算机学报》
摘要:该文介绍了形式规约语言 L FC设计的一些主要方面 ,并通过例子说明了 L FC的一些特色 .形式规约语言L FC是为支持软件形式规约的获取工作而开发的 .该语言以一种新的递归函数 ,即定义在上下文无关语言上的递归函数为基础 ,以上下文无关语言为数据类型 ,在语言级支持规约获取 .L FC语言已被用作形式规约获取系统 SAQ的一部分 .使用表明 ,L FC是一个能力强、易使用的语言 ,适合软件形式规约获取之用 ,并且适合其它一些用途
上下文无关语言上的递归函数:——Ⅰ.CFPRF及CFRF的定义
2002年 -董韫美-《中国科学:E辑》
摘要:建立上下文无关语言(CFL)上的递归函数理论,在CFL上定义了函数类CFRF和它的真子为CFPRF,它们可用来十分直接地表述非数值加工算法,事实上它们分别就是上下文无关语言上的偏递归函数和原始递归函数,提出了证明CFPRF函数性质的结构归纳法,给出一种枚举CFL句子的方法,定义了极小算子,基于CFL句子枚举,提出了极小算子的求值方法,最后,讨论了以CFRF为理论基础的可执行规约语言的设计和实现原则。
共[22]条   第下一页 末页 共[5]页
地址:北京市西城区冰窖口胡同2号   邮政信箱:北京8068信箱   邮编:100088    关于我们
电话:010-59300004   邮箱:ysg@ckcest.cn
Copyright © 2012 CKCEST ICP备案号:京ICP备14021735号-2