下推自动机的状态转换图与下推自动机的化简 被引量：10

1

作者 张继军 吴哲辉 《计算机科学》 CSCD 北大核心 2006年第3期271-274,共4页

参照有限状态自动机图形表示方式的思想方法,研究了标准下推自动机的图形表示——PAD 状态转换图,证明了下推自动机与标准下推自动机的等价性。给出了对标准下推自动机进行化简的原则,并给出了化简算法,实现了下推自动机的化简。

关键词 状态转换图 标准下推自动机 化简 行为等价 状态等价

在线阅读 下载PDF 职称材料

基于量子逻辑的下推自动机与上下文无关文法 被引量：8

2

作者 韩召伟 李永明 《软件学报》 EI CSCD 北大核心 2010年第9期2107-2117,共11页

给出基于量子逻辑的下推自动机(l-VPDA)的概念,提出广义的子集构造方法,进而证明了一般的l-VPDA与状态转移为分明函数且具有量子终态的l-VPDA的等价性.利用此等价性,给出了量子上下文无关语言的代数刻画与层次刻画,并籍此证明了量子上... 给出基于量子逻辑的下推自动机(l-VPDA)的概念,提出广义的子集构造方法,进而证明了一般的l-VPDA与状态转移为分明函数且具有量子终态的l-VPDA的等价性.利用此等价性,给出了量子上下文无关语言的代数刻画与层次刻画,并籍此证明了量子上下文无关语言关于正则运算的封闭性.最后,说明了量子下推自动机和量子上下文无关文法(l-VCFG)的等价性. 展开更多

关键词 量子逻辑 正交模格 量子下推自动机 量子上下文无关语言 量子上下文无关文法

在线阅读 下载PDF 职称材料

一个基于下推自动机的Web测试自动执行器 被引量：2

3

作者 贾晓霞 刘昶 +3 位作者 吴际 柳永坡 金茂忠 刘超 《计算机科学》 CSCD 北大核心 2006年第4期269-273,共5页

随着 Web 应用系统的广泛应用,对其质量要求也越来越高。如何进行有效的测试以保证 Web 应用系统的质量是值得关注的研究问题。支持测试用例自动执行的测试执行器(Test runner)是其中的一个热点和难点。文章研究并提出了基于下推自动机... 随着 Web 应用系统的广泛应用,对其质量要求也越来越高。如何进行有效的测试以保证 Web 应用系统的质量是值得关注的研究问题。支持测试用例自动执行的测试执行器(Test runner)是其中的一个热点和难点。文章研究并提出了基于下推自动机的 Web 测试自动执行器,并实现了其原型系统。该执行器支持测试用例的自动执行并给出测试结果报告,并通过 Web 应用测试实例验证了其有效性。 展开更多

关键词 测试自动执行器 下推自动机 WEB测试

在线阅读 下载PDF 职称材料

基于DNA下推自动机二进制减法和乘法的实现 被引量：1

4

作者 程珍 黄玉芳 周康 《计算机学报》 EI CSCD 北大核心 2009年第12期2338-2346,共9页

提出了基于DNA下推自动机二进制减法和乘法的实现方法.一位二进制借位减法,是通过预先构造好的DNA下推自动机模型在一个试管中以该模型的运行方式自动完成运算.m位二进制借位减法,是在一位二进制减法的基础上,按照从低位到高位的顺序,... 提出了基于DNA下推自动机二进制减法和乘法的实现方法.一位二进制借位减法,是通过预先构造好的DNA下推自动机模型在一个试管中以该模型的运行方式自动完成运算.m位二进制借位减法,是在一位二进制减法的基础上,按照从低位到高位的顺序,将低位产生的借位作为高位试管操作中的输入符号串,从而完成高位的减法运算.两位二进制乘法中包含移位和加法操作,在两个试管中分别设计好DNA下推自动机模型,分别完成被乘数与乘数各位的移位操作,同时结合相应的生物操作,将其作为另一个试管加法操作中的输入符号串,则加法操作中产生的结果即为所求.在此基础上,m位二进制乘法可通过移位操作的并行性和加法操作的串行性来完成运算.这些实现方法为DNA下推自动机实现基本的算术运算提供了比较完整的运算机制. 展开更多

关键词 DNA下推自动机 借位减法 乘法 移位操作 DNA编码

在线阅读 下载PDF 职称材料

基于下推自动机的XML数据流递归查询研究 被引量：1

5

作者 张晓琳 李宏辉 韩剑锋 《计算机工程与设计》 CSCD 北大核心 2010年第4期763-766,共4页

针对具有子孙轴(//)和谓词([])结构特征的XPath对具有不同递归深度的XML数据流进行递归查询处理问题,提出了基于下推自动机技术的处理方法,通过将XPath各类置步转化成相对应的处理模块,由算法将各类处理模块组合起来,建立了自上而下的... 针对具有子孙轴(//)和谓词([])结构特征的XPath对具有不同递归深度的XML数据流进行递归查询处理问题,提出了基于下推自动机技术的处理方法,通过将XPath各类置步转化成相对应的处理模块,由算法将各类处理模块组合起来,建立了自上而下的树状查询模型。由于查询过程中将会发生多重匹配,从而会产生大量的匹配模式,该模型通过有效的匹配策略和缓存操作,对匹配模式进行保存及检验,成功地实现XML数据流递归查询。实验结果表明,该算法在性能上要优于传统方法。 展开更多

关键词 XML数据流 多重匹配 下推自动机 递归查询 树状查询模型

在线阅读 下载PDF 职称材料

格值下推自动机与格值上下文无关文法 被引量：8

6

作者 彭家寅 《计算机工程与应用》 CSCD 北大核心 2011年第25期34-38,48,共6页

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下... 引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。 展开更多

关键词 格半群 格值下推自动机 格值上下文无关文法 格值语言 格值Chomsky范式文法

在线阅读 下载PDF 职称材料

基于下推自动机的细粒度锁自动重构方法 被引量：1

7

作者 张杨 邵帅 张冬雯 《软件学报》 EI CSCD 北大核心 2021年第12期3710-3727,共18页

针对粗粒度锁会严重影响并发程序的可伸缩性问题,提出一种面向细粒度锁的自动重构方法.该方法借助访问者模式分析、别名分析、负面效应分析等多种程序分析技术获取临界区代码的读写模式,然后使用下推自动机构建不同锁模式的识别方法,根... 针对粗粒度锁会严重影响并发程序的可伸缩性问题,提出一种面向细粒度锁的自动重构方法.该方法借助访问者模式分析、别名分析、负面效应分析等多种程序分析技术获取临界区代码的读写模式,然后使用下推自动机构建不同锁模式的识别方法,根据识别结果进行代码重构.与以往锁重构方法的不同之处在于,该方法考虑了锁降级模式,使重构适用性更广.基于此方法,在Eclipse JDT框架下,以插件的形式实现了自动重构工具FLock.在实验中,从重构个数、改变的代码行数、重构时间、准确性和重构后程序性能等方面对FLock进行了评估,并与已有的重构工具Relocker和CLOCK进行了对比.对HSQLDB,Jenkins和Cassandra等11个大型实际应用程序的重构结果表明:FLock共重构了1757个内置监视器对象,每个程序重构平均用时17.5s.该重构工具可以有效地实现粗粒度锁到细粒度锁的转换,与手动重构相比,有效提升了细粒度锁的重构效率. 展开更多

关键词 细粒度锁 读写锁 重构 下推自动机 程序分析

在线阅读 下载PDF 职称材料

Fuzzy 2型属性文法与Fuzzy属性下推自动机 被引量：5

8

作者 彭家寅 《四川师范大学学报（自然科学版）》 CAS CSCD 1999年第3期260-264,共5页

讨论了２型属性文法与属性下推自动机的关系，进一步给出了Ｆｕｚｙ上下文无关属性文法与Ｆｕｚｙ属性下推自动机，并详细讨论了二者的关系。

关键词 2型属性文法 属性下推自动机 模糊模式识别

在线阅读 下载PDF 职称材料

识别Fuzzy上下文无关语言的下推自动机(英文) 被引量：3

9

作者 舒兰 《电子科技大学学报》 EI CAS CSCD 北大核心 1992年第2期187-190,共4页

首先提出了Fuzzy下推自动机的概念,进而讨论了Fuzzy上下文无关文法与Fuzzy下推自动机的关系,即当且仅当一种Fuzzy语言是由Fuzzy上下文无关文法产生时,该语言可由Fuzzy下推自动机识别,从而达到了自动识别Fuzzy上下文无关语言的目的。

关键词 模式识别 FUZZY 下推自动机 文法

在线阅读 下载PDF 职称材料

Fuzzy下推自动机与Fuzzy上下文无关语言的关系 被引量：4

10

作者 彭家寅 《四川师范大学学报（自然科学版）》 CAS CSCD 2000年第1期27-30,共4页

在文献 (JournalofUESTofChina ,1992 ,2 1( 2 ) :188～ 190 )基础上 ,讨论了Fuzzy下推自动机按两种不同方式所接受的语言类的等价性 ,进而研究了Fuzzy下推自动机所产生的语言与Fuzzy上下文无关语言的等价关系 。

关键词 Fuzzy语言 Fuzzy下推自动机 上下文无关语言

在线阅读 下载PDF 职称材料

基于量子逻辑的下推自动机的代数刻画 被引量：1

11

作者 韩召伟 李永明 《计算机工程与科学》 CSCD 2008年第11期72-74,共3页

首先,本文提出量子下推自动机(简记为L-VPDA)的概念,从代数角度出发详细研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用量子状态构造证明了任意L-VPDA与状态转移为经典函数且具有量子终状态的L-VPDA间的相互等价性;其次... 首先,本文提出量子下推自动机(简记为L-VPDA)的概念,从代数角度出发详细研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用量子状态构造证明了任意L-VPDA与状态转移为经典函数且具有量子终状态的L-VPDA间的相互等价性;其次详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。 展开更多

关键词 量子逻辑 正交模格 量子下推自动机 量子上下文无关语言 代数刻画

在线阅读 下载PDF 职称材料

最大乘积型Fuzzy上下无关文法与下推自动机 被引量：1

12

作者 张诗静 舒兰 《模糊系统与数学》 CSCD 北大核心 2006年第6期73-76,共4页

在文献[1]的基础上,讨论了最大乘积型Fuzzy上下文无关文法与最大乘积型Fuzzy下推自动机的关系,即:由给定的最大乘积型Fuzzy上下文无关文法可构造一个最大乘积型Fuzzy下推自动机使得二者接受的语言集相同,反之亦然。从而达到自动识别语... 在文献[1]的基础上,讨论了最大乘积型Fuzzy上下文无关文法与最大乘积型Fuzzy下推自动机的关系,即:由给定的最大乘积型Fuzzy上下文无关文法可构造一个最大乘积型Fuzzy下推自动机使得二者接受的语言集相同,反之亦然。从而达到自动识别语言的目的。 展开更多

关键词 最大乘积型Fuzzy上下文无关文法 最大乘积型Fuzzy下推自动机 最大乘积型Fuzzy上下文无关语言

在线阅读 下载PDF 职称材料

有无1墨水点亚对数空间限定交替式下推自动机之间的关系

13

作者 徐建良 孙剑 +1 位作者 陈勇 孟庆春 《青岛海洋大学学报（自然科学版）》 CSCD 北大核心 2003年第3期449-456,共8页

该文引入 1墨水点 2方向交替式下推自动机 ,它是 1个具有额外能力的 2方向交替式下推自动机 ,能够用 1个墨水点在输入带上标记出最多 1个单元格。对具有 1个墨水点的和没有墨水点的亚对数空间限定交替式下推自动机之间的关系进行研究。... 该文引入 1墨水点 2方向交替式下推自动机 ,它是 1个具有额外能力的 2方向交替式下推自动机 ,能够用 1个墨水点在输入带上标记出最多 1个单元格。对具有 1个墨水点的和没有墨水点的亚对数空间限定交替式下推自动机之间的关系进行研究。实例证明了具有 展开更多

关键词 墨水点 交替式下推自动机 亚对数空间限定 图灵机模型 交替性

在线阅读 下载PDF 职称材料

最大乘积型Fuzzy上下文无关文法与下推自动机

14

作者 谢跃美 田莉萍 万会芳 《西南交通大学学报》 EI CSCD 北大核心 2006年第3期341-343,共3页

为了扩大现有研究的应用范围,基于最大乘积型Fuzzy文法与自动机引入了最大乘积型Fuzzy下推自动机的概念,并讨论了最大乘积型Fuzzy上下文无关文法与最大乘积型Fuzzy下推自动机的关系.研究表明,当且仅当最大乘积型Fuzzy上下文无关文法产... 为了扩大现有研究的应用范围,基于最大乘积型Fuzzy文法与自动机引入了最大乘积型Fuzzy下推自动机的概念,并讨论了最大乘积型Fuzzy上下文无关文法与最大乘积型Fuzzy下推自动机的关系.研究表明,当且仅当最大乘积型Fuzzy上下文无关文法产生的语言集能被最大乘积型Fuzzy下推自动机接受时,能达到自动识别最大乘积Fuzzy上下文无关语言的目的. 展开更多

关键词 最大乘积型Fuzzy 上下文无关文法 最大乘积型Fuzzy下推自动机 Fuzzy模式识别

在线阅读 下载PDF 职称材料

基于DNA计算的分子下推自动机(英文)

15

作者 张征 刘洁 石晓龙 《计算机学报》 EI CSCD 北大核心 2008年第12期2168-2172,共5页

DNA分子计算的工作原理是对生物系统进行编码,以生物化学反应为基础,利用生物技术实现生物系统的状态转移来推进计算过程.2001年以色列的Yaakov Benenson等人在基于DNA计算的发卡模型实现了具有状态转移功能的分子有限状态自动机,国内... DNA分子计算的工作原理是对生物系统进行编码,以生物化学反应为基础,利用生物技术实现生物系统的状态转移来推进计算过程.2001年以色列的Yaakov Benenson等人在基于DNA计算的发卡模型实现了具有状态转移功能的分子有限状态自动机,国内则有利用DNA计算的方法构造可编程分子下推存储器的相关研究.该存储器基于分子自动机的原理,能按一定逻辑进行自组装,是一种纳米尺度的生物存储机构.文中首先通过在分子有限自动机上扩展一个分子下推存储器从而获得了一种简单的分子下推自动机,并基于该下推自动机提出了一类语言的分子自动机解法.接着提出了两种改进的分子下推自动机的模型,通过增加模型复杂度,分别解决了基本型分子下推自动机存在输入字符串限制和输入分子形式不统一的问题.计算理论表明,该种下推自动机的计算能力超过了已有的有限自动机. 展开更多

关键词 分子下推自动机 DNA计算

在线阅读 下载PDF 职称材料

一种可自治下推自动机的DNA模型

16

作者 李汪根 丁永生 《上海大学学报（自然科学版）》 CAS CSCD 2004年第B10期97-99,共3页

本文在研究已有DNA计算机模型的基础上，提出了一种下推自动机的DNA实现模型，该模型可以用来接受回文语言．此模型(1)通过设计合适的动作函数实现了自动机的自治性；(2)运用一种限制性内切酶同时读取自动机的输入串符号和栈顶符号；(3... 本文在研究已有DNA计算机模型的基础上，提出了一种下推自动机的DNA实现模型，该模型可以用来接受回文语言．此模型(1)通过设计合适的动作函数实现了自动机的自治性；(2)运用一种限制性内切酶同时读取自动机的输入串符号和栈顶符号；(3)通过一系列酶切反应和酶连反应的循环模仿了下推自动机的运行；(4)其运行结果通过预先设计合适的检测分子报告． 展开更多

关键词 DNA模型 下推自动机 可自治 回文语言

在线阅读 下载PDF 职称材料

人工免疫系统中淋巴细胞的下推自动机模型

17

作者 付杰 梁意文 《计算机工程》 EI CAS CSCD 北大核心 2005年第23期36-38,共3页

有些淋巴细胞的构造模型,如r-邻域位线性构造模型,识别能力不够强,尤其对正则表达式缺乏识别能力。该文以下推自动机模型为原理,提出了一种自动机模型的淋巴细胞,这种淋巴细胞具有比有限自动机更强的识别能力,同时利用相近的入侵具有相... 有些淋巴细胞的构造模型,如r-邻域位线性构造模型,识别能力不够强,尤其对正则表达式缺乏识别能力。该文以下推自动机模型为原理,提出了一种自动机模型的淋巴细胞,这种淋巴细胞具有比有限自动机更强的识别能力,同时利用相近的入侵具有相似性这一点,引进了一个经验队列,配合HMM中状态转移概率的概念,对状态转移进行评判。最后给出了模型具体的设计方案。 展开更多

关键词 人工免疫 淋巴细胞 下推自动机 HMM

在线阅读 下载PDF 职称材料

亚对数空间限定的多墨水点交替式下推自动机的闭包属性

18

作者 王建良 徐建良 《中国海洋大学学报（自然科学版）》 CAS CSCD 北大核心 2010年第10期109-112,120,共5页

交替式下推自动机是并行计算的一种模型,它的空间计算复杂性研究对于解明并行算法的内存消耗具有重要意义。复杂性语言族的闭包属性反映了具有一定复杂性空间的并行计算模型之间的组合关系。论文研究仅有全称状态的交替式下推自动机的... 交替式下推自动机是并行计算的一种模型,它的空间计算复杂性研究对于解明并行算法的内存消耗具有重要意义。复杂性语言族的闭包属性反映了具有一定复杂性空间的并行计算模型之间的组合关系。论文研究仅有全称状态的交替式下推自动机的闭包属性,这些自动机均具有多个墨水点和亚对数限定的存储空间.通过设立巧妙的证人语言,本文使用反证法证明了具有有限多个墨水点的仅有全称状态的交替式下推自动机在星号、保持长度的同态、以及与正则语言的连结等运算下是不封闭的。 展开更多

关键词 交替式下推自动机 对数以下空间限定 闭包属性 墨水点

在线阅读 下载PDF 职称材料

取值于赋值幺半群的加权下推自动机的代数性质 被引量：1

19

作者 付雯静 韩召伟 《陕西师范大学学报（自然科学版）》 CAS CSCD 北大核心 2017年第3期9-16,共8页

引入取值于赋值幺半群的加权下推自动机、标准型加权下推自动机的定义,证明了在双幺赋值幺半群框架下,加权下推自动机与标准型加权下推自动机相互等价,且以终态方式与以空栈方式识别语言的加权下推自动机能够识别相同的形式幂级数;在Cau... 引入取值于赋值幺半群的加权下推自动机、标准型加权下推自动机的定义,证明了在双幺赋值幺半群框架下,加权下推自动机与标准型加权下推自动机相互等价,且以终态方式与以空栈方式识别语言的加权下推自动机能够识别相同的形式幂级数;在Cauchy双幺赋值幺半群上,加权上下文无关语言对于和、连接、正克林闭包运算封闭。结果表明加权下推自动机的诸多性质并不依赖于赋值幺半群的分配律和结合律。 展开更多

关键词 赋值幺半群 双幺赋值幺半群 加权下推自动机 加权上下文无关语言

在线阅读 下载PDF 职称材料

自上而下分析与下推自动机

20

作者 高永建 《辽宁师范大学学报（自然科学版）》 CAS 1989年第4期34-37,共4页

本文是利用某些形式语言理论和自动机理论对编译程序的语法分析中一种方法——自上而下分析方法进行说明。

关键词 自下而上分析 下推自动机 编译程序

在线阅读 下载PDF 职称材料