确定型有穷自动机状态极小化的研究

在树图分割法基础上,对确定型有穷自动机的极小化进行了研究.利用树图分割法,可以在状态的3次方时间内对确定型有穷自动机状态进行极小化.

确定有穷状态自动机最小化算法的三点说明

确定有穷状态自动机最小化可提高词法分析程序的效率。本文简述了最小化的概念、算法,从基本概念出发分析了该算法初始分划如何构造,及在状态无后继和全部由终止状态构成时这两种特殊情况下的解决对策,并对原算法做了进一步的细化。

非确定型有穷自动机的极小化

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

一种基于有穷状态自动机的二维浅海声线追踪方法

给出了一种二维的浅海声线追踪方法,解决了声线的反射、折射、全反射等问题并快速地找出声线的路径。对于单步的声线追踪,声速剖面假定为水深的函数,利用Snell定律进行单步求算。用有穷状态自动机对浅海的声线追踪建模,给出了浅海声线追踪内在的状态及状态转移分析。同时,给出了本征声线搜取的方法。最后通过对特定声速剖面情况的数值解值和解析解值进行比较,验证了该方法的正确性,并且讨论了应用该方法应该注意的问题和方法中还有待解决的问题。数值仿真实验结果表明,这种方法能够追踪浅海声线路径,其数值解精度达10-4.该方法在匹配场层析、目标跟踪定位和其它领域的射线跟踪有着应用前景。

基于有穷状态自动机浅海声场仿真研究

提出一种用有穷状态自动机研究浅海声场的方法。应用Snell定律对单步的声线传播进行研究,分析了浅海声场内在的状态及状态转移特性,推导出浅海声场的有穷状态自动机。步长根据实验精度要求设定,仿真实验表明步长越小,精度越高,计算量越大。为了减小运算量,本征声线通过两次追踪不同步长的方法获得。数值仿真结果证明了该方法的可行性,其精度可以达10-4。该方法可望应用到光学和地震学等领域的射线传播研究中。

基于非确定有穷自动机的网络入侵容忍系统研究

入侵容忍技术是继防火墙、存取控制、入侵检测技术之后的网络信息安全技术。当一个网络系统遭受非法入侵后,入侵容忍系统仍能及时自我诊断、恢复和重构,并能为合法用户提供所需的全部或者降级的服务。本文依据非确定性有穷自动机理论,模拟计算机受到攻击时入侵容忍系统的工作过程,为入侵容忍技术的发展提供了一种方法。

基于有穷自动机的自然语言状态转换

针对Robocup自主机器人比赛中,机器人进攻和防守状态、动作转换延迟问题,采用一种基于有穷自动机模型的自然语言状态转换方法,把机器人、环境等自然语言信息抽象成形式化的符号和状态,并转化为有穷自动机输入符号.通过设定状态转移函数、字母表规则、无差别地完成各种状态转换过程.研究结果表明:该方法能有效地完成自然语言状态下的机器人状态、动作间的转换,具有较好的实时性和可靠性.

基于有穷状态自动机原理的粉状物料运输车智能卸料控制程序

控制程序是粉状智能物料运输车完成自动卸料过程的关键,控制程序设计的好坏决定卸料过程能否顺利完成。针对新型粉状物料运输车智能卸料控制器,采用基于消息传递机制和有限状态机原理的多分支结构,程序结构简单清晰,容易编写、调试、功能扩展。

视觉导航有穷自动机在自然语言状态中的应用

室内移动机器人自主导航是一系列自然语言状态与动作转换结果,有效地控制和描述机器人状态和动作转换是自主导航过程的关键。本文首先利用视觉传感器获取障碍物YUV色彩空间信息,采用区域增长法识别障碍物连通域,将机器人状态以及控制指令转化为抽象的形式符号并建立状态转移函数,进而建立基于视觉导航机器人有穷自动机模型。实验结果表明,该方法能平滑、准确地完成自然语言状态下的机器人自主导航过程,具有较高的实时性和鲁棒性。

CAD系统中嵌套有穷状态自动机的设计与实现

基本CAD系统中都要用到有穷自动机,在一般的CAD系统中,通常用switch、case语句来设计相应的状态图,这样做不但在状态复杂时逻辑上容易出错,而且使多个开发者无法同时开发和调试自动机的几个子模块,一定程度上限制了开发并行性和进度,非嵌套有穷自动机的设计基本上模仿状态图的逻辑设计,让状态图的设计者可以像画状态图一样直观地设计自动机,增加了逻辑上的清晰性。在此基础上改造的嵌套有穷自动机有效地实现了多个开发者对某一自动机子功能的并行设计和单元测试,能有效地提高开发效率。

基于紧凑型有穷自动机模型的告警相关处理

在网络管理领域 ,告警相关 (Alarm Correlation)是取代简单告警过滤机制的一种全新故障管理策略 .通过在非确定型有穷自动机 (ndfa)的定义中引入状态基 (State Cardinality)的概念 ,本文首先给出紧凑型有穷自动机 (cfa)的定义 ,然后提出了基于紧凑型有穷自动机的告警相关处理模型并进行了详尽的描述 .在一个电信管理网 (TMN)的故障管理子系统中应用该模型对大量的告警信息在时间上和空间上进行告警相关处理 .仿真结果表明 ,基于紧凑型有穷自动机的告警相关处理模型的算法实现具备简单、高效、实用和实时的特点 。

汉字有穷自动机的优化及相关算法研究

在研究了汉字有穷自动机可以表示的语言基础上,引进了最小状态汉字有穷自动机和可区分状态的概念,并利用汉字有穷自动机间的等价性和可区分状态的性质,给出了一种最小化算法,实验证明,此算法优于最小化汉字有穷自动机算法.

基于有穷自动机的自动信任协商策略

自动信任协商通过协商策略协调协商双方间访问控制策略、信任证的交互披露以逐步建立信任.现有的访问控制策略规则的理论表示缺乏直观性,在分析和构造策略算法时带来不便.本文将有穷自动机形式化定义与自动信任协商相结合,提出一套基于有穷自动机的信任协商定义体系,并构造有穷自动机状态转换图对相应的访问控制策略进行图形化表示,便于分析和构造协商策略.针对积极策略缺乏安全性和谨慎策略缺乏高效性的问题,提出了基于有穷自动机的协商策略,该策略在谨慎策略的基础上加入记忆链结构,以减少协商双方交互次数,提高协商效率.经证明,该策略具备完备性和安全性,并通过仿真实验证明相对于谨慎策略,该策略具备高效性.

基于有限状态自动机的Web服务组合(英文)

Web服务是Web上的特殊软件资源,可以被应用系统发现和调用。如何根据用户的需求(目标服务)来组合Web服务是研究中需要解决的重要问题。通过使用有限状态自动机,服务组成的社区中的状态和操作可以使用有限状态自动机来模拟,这样可以表示服务操作的内部和外部概要。结合确定性动态命题逻辑,可以根据已有的Web服务,解决目标服务的可组合问题,产生组合计划。同时讨论了算法的复杂性。

有穷自动机在车辆管理系统开发中的应用

利用有穷自动机理论对"企业车辆管理"的生命周期状态转化进行了形式化描述.通过分析车辆管理的流程,得到了车辆管理所涉及的各项业务流程,并对各项业务进行了说明,使得车辆管理的业务流程更加清晰.

基于自动机的设备维修状态演化模型研究

目前采用维修文档记录与管理每次设备维修活动,对于设备维修过程没有建立模型,导致设备维修信息缺乏系统性。为此在逻辑层次建立设备维修状态演化模型,对设备维修过程进行定性描述。在分析设备维修过程的动力学特性的基础上,提出维修状态项与维修状态的概念。维修状态项的所有维修事件被归纳为恢复性维修事件、换改型维修事件以及设备改造型维修事件这3类维修事件,维修状态项的维修过程被归纳A/B/C这3种维修模式,在每种维修模式下,维修状态项的维修过程被分解为维修事件序列以及维修状态转移序列,维修状态转移序列被维修事件序列驱动与控制,两类符号序列之间的逻辑关联采用有穷自动机进行形式化的定义,从而建立设备维修状态演化模型。最后以碳酸吹瓶机的设备维修状态演化模型为案例进行例证。

一类有穷自动机的设计

讨论了一类有穷自动机与形式语言二者之间的关系,给出了一类语言与对应的自动机(包括确定型的有穷自动机与不确定型的有穷自动机)二者之间相互转换的方法,最后指出了这个方法可以适用于类似问题的求解。

基于量子逻辑的几类有穷自动机之间的关系

根据初始状态和终止状态是否为分明的,非确定型量子有穷自动机可分为四类,确定型量子有穷自动机可分为三类.本文详细讨论了四类非确定型量子有穷自动机之间的关系以及三类确定型量子有穷自动机之间的关系,并且利用新的构造方法,证明了初态为分明的确定型量子有穷自动机与终态为分明的确定型量子有穷自动机是等价的.这些结论为实际应用中计算模型的合理选取提供了理论依据.

有穷自动机等价转化中的一种重要工具

有穷自动机的等价转化,主要包括不确定有穷自动机(NFA)的确定化,确定有穷自动机(DFA)的最小化。着重探讨了这两个算法中的一种常用的重要工具——状态转换矩阵,以及用状态转换矩阵解决几类特殊问题的方法。

模糊识别器与有穷自动机的等价性

针对模糊识别器与有穷自动机的关系,证明了当输入字母表相同时,任给一个模糊识别器,必然存在一个有穷自动机,使得模糊识别器的行为与有穷自动机所接受的语言相同;反之,任给一个有穷自动机,必然存在一个模糊识别器,使得有穷自动机所接受的语言与模糊识别器的行为相同,从而得出它们之间的等价性。