PSL构造双向交换自动机及非确定自动机的方法

1

作者 虞蕾 陈火旺 《软件学报》 EI CSCD 北大核心 2010年第1期34-46,共13页

PSL(property specification language)是一种用于描述并行系统的属性规约语言,包括线性时序逻辑FL(foundation language)和分支时序逻辑OBE(optional branching extension)两部分.由于OBE就是CTL(computation tree logic),并且具有时... PSL(property specification language)是一种用于描述并行系统的属性规约语言,包括线性时序逻辑FL(foundation language)和分支时序逻辑OBE(optional branching extension)两部分.由于OBE就是CTL(computation tree logic),并且具有时钟声明的公式很容易改写成非时钟公式,因此重点研究了非时钟FL逻辑.为便于进行模型检验,每个FL公式必须转化成为一种可验证形式,通常是自动机(非确定自动机).构造非确定自动机的过程主要是通过中间构建交换自动机来实现.详细给出了由非时钟FL构造双向交换自动机的构造规则.构造规则的核心逻辑不仅仅局限于是在LTL(linear temporal logic)基础上的正规表达式,而且全面而充分地考虑了各种FL操作算子的可能性.并且给出了将双向交换自动机转化为非确定自动机的一种方法.最后,编写了将PSL转化为上述自动机的实现工具.FL双向交换自动机的构造规则计算复杂度仅是FL公式长度的线性表达式,验证了构造规则的正确性.在此基础上,证明了双向交换自动机与其转化的等价的非确定自动机接受的语言相同.上述工作对解决复杂并行系统建模和模型验证问题具有重要的理论意义和应用价值. 展开更多

关键词 PSL(property specification language) FL(foundation language) 双向交换自动机 非确定自动机 模型检验

在线阅读 下载PDF 职称材料

P2P网络中基于非确定有限自动机的XML数据流过滤 被引量：1

2

作者 沈洁 印桂生 王向辉 《吉林大学学报（工学版）》 EI CAS CSCD 北大核心 2012年第1期134-139,共6页

将自动机方法对XML数据的过滤延伸到P2P网络中,依据在本地XML系统YFilter中构造非确定有限自动机(NFA)的思想,采用Chord环建立起分布式的NFA对于peer节点中的XML数据的查询过滤系统,并基于递归法执行查询过滤,在不同的peer节点上得到满... 将自动机方法对XML数据的过滤延伸到P2P网络中,依据在本地XML系统YFilter中构造非确定有限自动机(NFA)的思想,采用Chord环建立起分布式的NFA对于peer节点中的XML数据的查询过滤系统,并基于递归法执行查询过滤,在不同的peer节点上得到满足查询条件的数据集合。通过实验验证了当查询的数量和网络大小发生变化时分布式NFA的方法的执行性能。结果表明:本文方法可在不同的过滤场景中处理百万数量级的XPath查询,具有良好的网络流量和过滤延迟。 展开更多

关键词 计算机应用 XML 对等网 非确定有限自动机 过滤

在线阅读 下载PDF 职称材料

非确定型有穷自动机的极小化 被引量：5

3

作者 李翰芳 许道云 《吉林大学学报（理学版）》 CAS CSCD 北大核心 2007年第4期582-588,共7页

利用自动机状态集上的等价关系对自动机的状态集进行极小化,从而得到与原自动机功能等价的极小化自动机.通过两台确定型有穷自动机(DFA)的连接,构造一台非确定型有穷自动机(NFA).利用这两台确定型有穷自动机状态集上的等价关系,可以构... 利用自动机状态集上的等价关系对自动机的状态集进行极小化,从而得到与原自动机功能等价的极小化自动机.通过两台确定型有穷自动机(DFA)的连接,构造一台非确定型有穷自动机(NFA).利用这两台确定型有穷自动机状态集上的等价关系,可以构造这台非确定型有穷自动机状态集上的等价关系,从而对这台非确定型有穷自动机进行极小化.结果表明这台非确定型有穷自动机的极小化自动机的状态复杂度,不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度;并且自动机在等价关系基础上进行极小化时不改变识别语言. 展开更多

关键词 确定型有穷自动机 非确定型有穷自动机 等价关系 状态极小化

在线阅读 下载PDF 职称材料

一种非确定型有穷自动机的极小化方法

4

作者 张丽 《宁夏大学学报（自然科学版）》 CAS 2012年第2期148-151,共4页

自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言.确定型有穷状态自动机(DFA)极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机.而非确定型有穷状态自动... 自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言.确定型有穷状态自动机(DFA)极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机.而非确定型有穷状态自动机(NFA)极小化问题尚未找到有效算法.尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加.从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机. 展开更多

关键词 自动机 非确定型自动机 子语言自动机 同态 极小化

在线阅读 下载PDF 职称材料

有限状态自动机的并行确定化及过程分析 被引量：5

5

作者 孙玉强 刘三阳 +1 位作者 王明斐 邹凌 《计算机科学》 CSCD 北大核心 2006年第10期293-294,F0003,共3页

本文通过对并行环境下非确定有限自动机和确定有限自动机的等价性和转换进行研究,详细分析了非确定有限自动机到确定有限自动机的并行转换方法及算法,并以实例给出了其间并行转化的过程。

关键词 并行转换 非确定有限自动机 确定有限自动机

在线阅读 下载PDF 职称材料

增加结构非循环模糊自动机最小化算法(英文) 被引量：1

6

作者 胡红莉 莫智文 《工程数学学报》 CSCD 北大核心 2006年第4期599-606,共8页

我们提出了一种新的不完全的增加结构算法,该算法结合了非循环确定模糊自动机的性质。由于该算法与隶属度有关,因此算法给出了与传统方法不同的运算函数,而且通过构造模拟状态使该算法可在有多输入状态的条件下运行。所以这个新的不完... 我们提出了一种新的不完全的增加结构算法,该算法结合了非循环确定模糊自动机的性质。由于该算法与隶属度有关,因此算法给出了与传统方法不同的运算函数,而且通过构造模拟状态使该算法可在有多输入状态的条件下运行。所以这个新的不完全增加结构算法较传统算法更可行和实用。新算法由两部分构成:增加模糊字符串到最小非循环确定模糊自动机和最小化增加模糊字符串后得到的自动机。因为在增加模糊字符串到最小非循环确定模糊自动机的过程中,运用了一些相关的新函数,所以得到的自动机仍然是确定的,而且没有增加任何无关的字符串到自动机的可识别语言。 展开更多

关键词 非循环确定模糊自动机 模糊字符串 不完全增加结构算法 构造模拟状态 非必要隶属度状态

在线阅读 下载PDF 职称材料

基于自动机原理的自动售货机软件的实现 被引量：4

7

作者 胡德敏 杨伟民 +1 位作者 高建 范祺 《上海理工大学学报》 CAS 北大核心 2003年第1期99-102,共4页

利用自动机原理对现有的自动售货机的工作模式进行了分析,指出了自动售货机在购买多种商品时的不方便之处和销售管理上的落后现象,提出了用软件方法对自动售货机工作模式进行优化和扩展,并增强其管理功能,以使自动化销售过程更快捷、准... 利用自动机原理对现有的自动售货机的工作模式进行了分析,指出了自动售货机在购买多种商品时的不方便之处和销售管理上的落后现象,提出了用软件方法对自动售货机工作模式进行优化和扩展,并增强其管理功能,以使自动化销售过程更快捷、准确和有效. 展开更多

关键词 非确定性有限自动机 确定性有限自动机 信息交互

在线阅读 下载PDF 职称材料

关于有限自动机定义的一个注记 被引量：1

8

作者 韩光辉 曾诚 《电脑与信息技术》 2015年第4期1-4,共4页

给出了有限自动机的一般定义M=(Q,Σ,R,q0,F),其中R哿(Q×(Σ∪{ε}))×Q,特别地,如果R:Q×Σ→Q,则M是确定性有限自动机,该定义统一描述了确定性有限自动机、非确定性有限自动机、带空转移的非确定性有限自动机与部分自动... 给出了有限自动机的一般定义M=(Q,Σ,R,q0,F),其中R哿(Q×(Σ∪{ε}))×Q,特别地,如果R:Q×Σ→Q,则M是确定性有限自动机,该定义统一描述了确定性有限自动机、非确定性有限自动机、带空转移的非确定性有限自动机与部分自动机的概念。在该定义下,证明了确定性有限自动机与非确定性有限自动机的等价性以及正则语言类关于连接、闭包运算的封闭性,因此该定义在理论上是完备的。 展开更多

关键词 有限自动机 确定性有限自动机 非确定性有限自动机 部分自动机 正则语言

在线阅读 下载PDF 职称材料

入侵检测系统中模式匹配自动机的构造研究

9

作者 吴绍根 李洛 《微型电脑应用》 2006年第5期10-12,2,共3页

本文提出了一种新的用于构造入侵检测模式匹配自动机的方法。该方法从构造判定单个模式的NFA自动机入手,通过集成单个的NFA而得到全集的NFA,并将全集NFA转换为与之等价的DFA并化简,从而可得到全集的确定型模式匹配有限自动机。由于该方... 本文提出了一种新的用于构造入侵检测模式匹配自动机的方法。该方法从构造判定单个模式的NFA自动机入手,通过集成单个的NFA而得到全集的NFA,并将全集NFA转换为与之等价的DFA并化简,从而可得到全集的确定型模式匹配有限自动机。由于该方法可以完全自动完成,从而可以方便地为入侵检测系统构造模式匹配自动机。 展开更多

关键词 入侵检测系统 确定型有限自动机 非确定型有限自动机 等价性

在线阅读 下载PDF 职称材料

一种构造入侵检测系统模式匹配自动机的方法

10

作者 吴绍根 李洛 《安徽电气工程职业技术学院学报》 2006年第1期84-87,共4页

介绍了一种新的用于构造入侵检测系统模式匹配自动机的方法,该方法的基本出发点在于NFA与DFA能力的等价性、构造NFA的方便性和DFA运行的高效性。它从构造判定单个模式的NFA自动机入手,通过集成单个的NFA而得到全集的NFA,并将全集NFA转... 介绍了一种新的用于构造入侵检测系统模式匹配自动机的方法,该方法的基本出发点在于NFA与DFA能力的等价性、构造NFA的方便性和DFA运行的高效性。它从构造判定单个模式的NFA自动机入手,通过集成单个的NFA而得到全集的NFA,并将全集NFA转换为与之等价的DFA并化简,从而可得到全集的确定型模式匹配有限自动机。由于该方法可以完全自动完成,从而可方便地为入侵检测系统构造模式匹配自动机。 展开更多

关键词 入侵检测系统 确定型有限自动机 非确定型有限自动机 等价性

在线阅读 下载PDF 职称材料

判定非确定离散事件系统稳定性的梯度搜索算法 被引量：1

11

作者 舒少龙 林峰 黄志强 《控制与决策》 EI CSCD 北大核心 2008年第3期346-348,共3页

讨论基于非确定自动机/形式语言模型的非确定离散事件系统(NDES)稳定性问题.引入非确定离散事件系统稳定性的定义,并得到了稳定性的判据定理.给出了基于梯度的搜索算法,该算法可有效消除观测器的冗余,从而降低了计算复杂度.

关键词 非确定离散事件系统 非确定自动机/形式语言 稳定性 梯度搜索

在线阅读 下载PDF 职称材料

基于有限状态自动机理论的CBTC系统列车管理方法研究 被引量：3

12

作者 王志平 耿鹏 孙晓光 《铁路通信信号工程技术》 2020年第11期63-69,共7页

针对C B T C系统中车地通信常见的功能需求,建立车地通信交互模型;通过有限状态自动机理论(F S A)对列车通信自动管理模型进行定义,并根据定义构造非确定有限自动机(NFA)和确定性有限自动机(DFA),完成创建列车管理状态自动机能够识别的... 针对C B T C系统中车地通信常见的功能需求,建立车地通信交互模型;通过有限状态自动机理论(F S A)对列车通信自动管理模型进行定义,并根据定义构造非确定有限自动机(NFA)和确定性有限自动机(DFA),完成创建列车管理状态自动机能够识别的语言,实现CBTC系统列车自动管理功能。 展开更多

关键词 CBTC系统 车地通信 列车管理 有限状态自动机 非确定的有限状态自动机 确定的有限状态自动机

在线阅读 下载PDF 职称材料

非确定型模糊有限自动机的一种新的极小确定化方法

13

作者 李平 杨巨芳 杨艳萍 《山东大学学报（理学版）》 CAS CSCD 北大核心 2024年第1期56-61,共6页

非确定型模糊有限自动机的极小确定化是自动机理论中的一个重要问题。在格序幺半群下,本文给出一种非确定型模糊有限自动机的新的极小确定化方法,称为内部构造法。为此,首先给出了模糊状态的内部的定义及其相关性质,进一步证明任给一个... 非确定型模糊有限自动机的极小确定化是自动机理论中的一个重要问题。在格序幺半群下,本文给出一种非确定型模糊有限自动机的新的极小确定化方法,称为内部构造法。为此,首先给出了模糊状态的内部的定义及其相关性质,进一步证明任给一个非确定型模糊有限自动机,利用模糊状态的内部的性质得到一个极小的确定型模糊有限自动机与之等价,最后通过例子验证该方法的正确性。 展开更多

关键词 格序幺半群 非确定型模糊有限自动机 确定型模糊有限自动机 极小确定化 内部构造

原文传递

判定非确定离散事件系统稳定性的多项式复杂度算法

14

作者 舒少龙 刘君 《控制理论与应用》 EI CAS CSCD 北大核心 2009年第11期1247-1250,共4页

本文讨论基于非确定自动机/形式语言模型的非确定离散事件系统稳定性的多项式算法.在引入拟距离的概念之后,根据拟距离形式化地定义了非确定离散事件系统稳定性.以往判定非确定离散事件系统稳定性的算法基于系统的观测器实现,该观测器... 本文讨论基于非确定自动机/形式语言模型的非确定离散事件系统稳定性的多项式算法.在引入拟距离的概念之后,根据拟距离形式化地定义了非确定离散事件系统稳定性.以往判定非确定离散事件系统稳定性的算法基于系统的观测器实现,该观测器在结构上具有指数复杂度,因此本文分析系统结构和观测器结构之间的关系,基于对系统状态对的讨论,提出了判定系统稳定性的有效多项式搜索算法. 展开更多

关键词 非确定自动机/形式语言模型 稳定性 梯度搜索 多项式复杂度

在线阅读 下载PDF 职称材料

非确定型离散事件系统双模拟控制的实现 被引量：6

15

作者 刘富春 《控制理论与应用》 EI CAS CSCD 北大核心 2015年第1期75-79,共5页

近年来,双模拟等价关系与离散事件系统监控理论相结合的研究引起了国内外许多学者的广泛关注.本文针对作者在前期工作中提出的非确定型离散事件系统的双模拟控制机制,进一步探讨其实现问题.利用投影映射对系统规范说明语言进行等价类划... 近年来,双模拟等价关系与离散事件系统监控理论相结合的研究引起了国内外许多学者的广泛关注.本文针对作者在前期工作中提出的非确定型离散事件系统的双模拟控制机制,进一步探讨其实现问题.利用投影映射对系统规范说明语言进行等价类划分,构造了一棵计算树,得到了一个判断规范说明是否具有基于模拟关系可观性的多项式算法,证明了双模拟控制机制是多项式时间算法可实现的.同时,通过对控制器配备具有存储和判断功能的模拟关系识别器,阐述了这种双模拟控制机制是物理可实现的. 展开更多

关键词 离散事件系统 监督控制 双模拟关系 非确定型自动机 双模拟控制

在线阅读 下载PDF 职称材料

非确定有限自动机的最短D1-同步字求解 被引量：1

16

作者 朱凯 毋国庆 +1 位作者 袁梦霆 杨磊 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2021年第2期68-73,共6页

研究了非确定有限自动机的最短D1-同步字的计算问题。针对这种自动机定义了D1W问题及其参数化版本问题p-D1W和最优问题shortest-p-D1W,证明了p-D1W和shortest-p-D1W分别属于para-NP和para-DP。利用均匀分布模型随机生成大量的非确定的... 研究了非确定有限自动机的最短D1-同步字的计算问题。针对这种自动机定义了D1W问题及其参数化版本问题p-D1W和最优问题shortest-p-D1W,证明了p-D1W和shortest-p-D1W分别属于para-NP和para-DP。利用均匀分布模型随机生成大量的非确定的有限自动机进行实验,结果表明:在定长的参数下几乎所有随机产生的自动机实例都不是D1-可同步的,一旦将自动机上每个状态和字母的变迁函数的像数量限制在2以内,会出现少量的D1-可同步的自动机,且绝大多数最短同步字长不超过状态数的2倍。 展开更多

关键词 非确定有限自动机 同步字 固定参数易解的归约 可满足问题 参数化复杂性 参数化算法

原文传递

基于前序关系的非确定型有穷自动机极小化算法 被引量：1

17

作者 张明明 秦永彬 《山东大学学报（理学版）》 CAS CSCD 北大核心 2010年第7期34-38,共5页

为了减少非确定型有穷自动机(non-deterministic finite automata,NFA)的状态数,引入前序关系,并以图论为工具,将NFA的转移图看作一个带有标记的有向图,给出了NFA极小化的一个新方法。与现行的利用归并等价状态来极小化NFA的算法相比,... 为了减少非确定型有穷自动机(non-deterministic finite automata,NFA)的状态数,引入前序关系,并以图论为工具,将NFA的转移图看作一个带有标记的有向图,给出了NFA极小化的一个新方法。与现行的利用归并等价状态来极小化NFA的算法相比,该方法可以使得NFA在接受语言的能力等价的前提下,状态数得到进一步的减少。 展开更多

关键词 非确定型有穷自动机 前序关系 状态合并 极小化

原文传递

非确定模糊有穷自动机的ε-语言逼近 被引量：1

18

作者 王海辉 赵路瑶 李平 《山东大学学报（理学版）》 CAS CSCD 北大核心 2021年第3期37-43,共7页

在max-*复合推理下引入了非确定模糊有穷自动机的概念,其中*是t-模运算。为了比较2个非确定模糊有穷自动机的行为,借助于[0, 1]上的一个实数ε,定义了2种ε-语言逼近,讨论了它们之间的关系。证明了非确定模糊有穷自动机和模糊有穷自动... 在max-*复合推理下引入了非确定模糊有穷自动机的概念,其中*是t-模运算。为了比较2个非确定模糊有穷自动机的行为,借助于[0, 1]上的一个实数ε,定义了2种ε-语言逼近,讨论了它们之间的关系。证明了非确定模糊有穷自动机和模糊有穷自动机之间是0-弱语言逼近的,即二者可以接受相同的模糊语言。此外,还讨论了2种ε-语言逼近的一些代数性质,特别地给出ε-语言逼近在并运算、*运算以及连接运算下的性质。最后,分析了ε-语言逼近的鲁棒性。 展开更多

关键词 模糊有穷自动机 非确定模糊有穷自动机 语言逼近 鲁棒性

原文传递

基于子集构造法的优化的NFA确定化算法 被引量：1

19

作者 任平红 陈矗 +1 位作者 曹宝香 禹继国 《计算机技术与发展》 2011年第1期70-73,共4页

使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题。为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法。首先定义了识别符的有效引出状态集概念... 使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题。为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法。首先定义了识别符的有效引出状态集概念并证明了ε-closure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的ε-closure的求算子算法,基于这两个子算法给出了优化的非确定有限自动机确定化算法,最后将算法应用于实例,实验结果表明计算量远小于子集构造法的计算量。相比子集构造法,算法能更有效地对非确定有限自动机进行确定化。 展开更多

关键词 子集构造法 非确定有限自动机 优化的 确定化算法

在线阅读 下载PDF 职称材料

基于局部乱序事件排序的复杂事件匹配方法

20

作者 夏秀峰 周清怡 +3 位作者 张杨 郗红梅 杨宏伟 邱涛 《计算机工程与设计》 北大核心 2024年第10期2986-2993,共8页

为处理乱序事件流上的复杂事件匹配问题,减少排序开销,在非确定有限状态自动机的基础上提出解析查询指导排序策略和匹配结果反馈排序策略。根据查询内容对事件流进行分解过滤,得到查询所需的子事件流,设计基于堆排序的子事件流合并算法... 为处理乱序事件流上的复杂事件匹配问题,减少排序开销,在非确定有限状态自动机的基础上提出解析查询指导排序策略和匹配结果反馈排序策略。根据查询内容对事件流进行分解过滤,得到查询所需的子事件流,设计基于堆排序的子事件流合并算法。通过匹配过程中自动机的状态,设计算法对自动机状态转移相关的事件实例进行排序。在股票数据集上进行实验,验证了提出方法相较于现有方法在匹配性能上有显著提升。 展开更多

关键词 复杂事件匹配 乱序事件流 非确定有限状态自动机 分解过滤 子事件流 堆排序 状态转移

在线阅读 下载PDF 职称材料