带空移动的加权有限自动机量化等价及其转换

在经典的有限自动机理论中,带空移动的有限自动机与不带空移动的有限自动机是等价的。取值于实数的加权有限自动机是自动机的一种推广模型,它给经典自动机的每个转换赋一个取值于实数的权值,这些权值表示执行转换的代价。为了研究带空移动的加权有限自动机与不带空移动的加权有限自动机是否具有等价性这一问题,提出量化等价的概念,并研究如何将一个带空移动的加权有限自动机转换为一个与之量化等价的不带空移动的加权有限自动机。研究结果表明:这两者是量化等价的。     

基于广义有限自动机的图像压缩方法

提出一种用确定性的广义有限自动机(GFA)对灰度图像进行压缩编码的方法.对一幅输入的数字化灰度图像,检测其中的自相似性,该图像可以被表示成一个广义有限自动机.解码算法可以非常高效的由确定的广义有限自动机复原图像,且结果图像没有很明显的方块效应.这种方法与传统的有限自动机方法相比具有状态数较少、压缩比高、压缩效果较好的优点.     

有限自动机理论在高速公路收费中的应用

阐述了有限自动机理论及其在高速公路车道收费控制中的应用 ,最后描述了系统硬件结构框图和软件设计。     

有限状态自动机在助力器检测设备中的应用

针对目前我国真空助力器检测设备的落后现状,采用有限状态自动机与现代控制技术开发了一种新型的汽车真空助力器设备的微机检测系统;通过对检测设备整个系统和各个分系统的动态行为分析,建立整个系统和各个分系统的状态机和子状态机并依据此模型开发出检测系统主控软件;应用结果表明,利用该方案设计的检测主控软件,增强了系统的可靠性与稳定性;软件结构清晰,易于维护和扩展。     

有限自动机在复合事件检测中的应用

针对早期系统只提供原子事件的检测机制,不能检测由原子事件组成的复合事件的问题,提出了用有限自动机来检测复合事件的方法.说明了复合事件的组成和表达式,利用自动机原理对复合事件的检测模式进行了分析,给出了复合事件检测的具体过程:从事件表达式到不确定的有限自动机,从不确定的有限自动机到最小化确定的有限自动机,再用程序实现了确定的有限自动机.实例表明,自动机模型是检测复合事件的一种有效实现方式.     

有限自动机在CMMB解复用中的应用研究

通过对中国移动多媒体广播（CMMB）系统复用帧结构的分析,运用有限自动机原理,提出终端解复用的一种设计方法。对终端接收到的码流进行分类,归纳出码流中各种信息的状态,根据各种状态之间的转换条件,设计出了有限自动机。用C代码实现后,可以看出该有限自动机不仅能很好地解析终端接收的码流,而且,解析后能将各种有用的信息保存起来,以供其他模块使用。     

元胞自动机在图像修补中的应用研究

提出了一种随机元胞自动机模型算法,使用邻域和迭代规则作用于图像的缺失部分,使缺失的部分通过吸收原有图像的数据进行自我修复。该方法的特点在于规则简单、容易实现,不需要针对特定图像设置先验参数,可以恢复任意的有缺失部分的数字图像,并且具有较高的运行速度。     

线性有限自动机输入输出集的性质

证明了两个线性有限自动机化合而得到的自动机具有输入输出均匀的性质,建立了由两个延迟1步弱可逆线性有限自动化合后得到的自动机的输入集个数与化合前自动机输入集个数的等式关系。     

灰度值加权医学图像融合方法

根据医学图像显像特点,说明医学图像融合在空域上研究的可行性,并针对灰度值极大法在颅脑图像融合中的不足做了改进,把图像的区域特征考虑在内,经反复实验比较,发现图像的平均梯度不仅能反映图像的清晰程度,同时还反映出图像中微小细节反差和纹理特征,提出了灰度值加权和的算法,以灰度值为基础,把平均梯度作为权值,结果证明,给定合适的权值大小,融合后的图像脑组织丰富清晰,并且相对变换域融合,计算量小,适用于实时性系统.     

二维细胞自动机在图像认证中的应用

传统的hash函数难以实现并行计算,用于图像认证时不能充分利用图像的特性。而二维细胞自动机的拓扑结构适用于图像,支持并行计算,且计算效率较高,由此提出一种基于二维细胞自动机的图像认证方法。理论分析与初步实验结果表明,细胞自动机随机性好、满足雪崩准则,效率高于传统的hash函数。     

非确定有穷自动机在盲文转码中的应用

对盲人使用的计算机交互技术进行研究是很有意义的工作。盲文字库缺少国际标准和不同公司的盲文字库不兼容造成了很多难题。将盲文用汉字点位编码表示,能摆脱盲文字库的束缚。用不确定有穷自动机描述盲文与汉字点位编码的转换过程,再用逆序拆分子集法对其确定化。经测试系统的转码正确率达到100%,从而实现盲文与机器无关,使得盲人使用计算机更方便。     

Representations of Regular Ideals in Finite Automata

Regular ideals of a free monoid are shown to be characterized by weak (noninitial) representations in finite automata. The class of kernel ideals is also shown to be invariant under the action of several automata functors and to be equal to the class of zero ideals.     

赋权型自动机的不同模型研究

自动机理论是理论计算机科学的基础理论之一,在很多领域自动机有着广泛的应用,有穷状态自动机是正则语言的识别机器,通常分为确定型与非确定型两种模型,其识别语言的能力是等价的。赋权自动机是另一类重要的自动机模型,自动机的每条转移规则和状态可以赋以某一代数结构上的某一数值,从而可以计算输入字符串的权值。任何有穷状态自动机都可以视为一特殊赋权自动机,因此赋权自动机功能更强大,应用更为广泛。     

数据关联的时序有限自动机模型的建模方法

介绍了一种用时序自动机为数据关联问题建模的方法，对数据关联问题的研究方法做了新的尝试。目前有多种数据关联算法，对这些方法的分析和评价成为急于解决的问题。鉴于观测信息的时序性，该文以有限自动机(FA)为基础，将时间序列引入到有限自动机中，定义了时序有限自动机(TFA)，建立了数据关联(DA)的时序有限自动机模型，用于判断关联算法得到的航迹准确性。     

基于元胞自动机的毫米波图像边缘检测

考虑到毫米波图像噪声较强、模糊严重的特点,本文在边缘提取之前对图像进行了去噪预处理,并将元胞自动机引入到多灰度级图像边缘提取中。试验结果,证明了该方法的有效性和优越性。     

弱可逆线性有限自动机的一种分解

讨论有限自动机的分解有助于分析弱可逆有限自动机的结构和求解弱逆.首先证明了弱同构的弱可逆有限自动机具有相似的分解形式;接着考虑了一类特殊的弱可逆线性有限自动机的分解, 从状态输出权的角度刻画了该分解存在的一个充分条件;然后把这种分解形式推广到了一般的弱可逆线性有限自动机上, 即:延迟τ步弱可逆线性有限自动机分解成延迟0步弱可逆有限自动机和一种特殊的有限自动机M\\-D, 并得到了分解存在的充要条件;最后, 用输出序列的代数性质来刻画其中的充分条件, 并把它转化成了一个矩阵的秩的计算.这种分解形式并不局限于n元弱可逆有限自动机, 而且分解条件也比较简单, 仅与输出序列的性质有关.     

Mizumoto格值有限自动机及其最小化

提出取值为格半群的Mizumoto格值有限自动机的概念,得到基于模糊字符串的Mizumoto格值有限自动机的扩张模型,并详细讨论了其性质。同时建立了扩张Mizumoto格值有限自动机与标准扩张Mizumoto格值有限自动机的等价性,在此基础上给出了其最小化算法。     

弱可逆有限自动机的分解

有限自动机公开钥密码体制的提出进一步激励了有限自动机可逆性的研究．在有限自动机公开钥密码体制中首次提出了自动机化合的概念．易知,两个弱可逆有限自动机的化合仍然是一个弱可逆有限自动机并且它的延迟步数不大于前两个有限自动机延迟步数之和．然而,另一方面,如何将一个弱可逆有限自动机分解为两个弱可逆有限自动机的化合却是一个非常困难的问题．该文主要考虑了一类n元严格延迟τ步弱可逆有限自动机M的延迟步数的分解问题．给出了一类特殊的n元弱可逆有限自动机分解的条件和结果．首先证明了如果对M中的每个状态s有T（s,τ）枝等,则M可分解为τ个延迟1步弱可逆有限自动机的化合．然后证明了M可分解为一个τ—m步弱可逆有限自动机和m阶延迟元的充要条件是对M中的每个状态s有T（s,m）枝等．     

线性有限自动机的同步序列及其生成算法

文章主要讨论了线性有限自动机的同步序列,得到了线性有限自动机有同步序列的充要条件,还讨论了一类输入存贮线性有限自动机及可等价嵌入输入存贮线性有限自动机的极小线性有限自动机的同步序列。最后给出了判断线性有限自动机有无同步序列以及求线性有限自动机(最短)同步序列的一些算法。     

有限精度时间自动机的可达性检测

为了缓解状态空间爆炸问题,减小模型检测过程中生成的状态空间,加快模型检测速度,引入有限精度时间自动机(finite precision timed automata,简称FPTA)作为实时系统的形式模型,并提出了一种数据结构SDS(series of delay sequence)符号化表示状态空间中的状态集.FPTA只记录时钟变量的整数值及时钟变化的先后次序,从而减小生成的状态空间.在一定的时间约束下,Alur与Dill提出的时间自动机的可达性检测可简化为FPTA的可达性检测.举例描述了状态空间的生成过程和表示方法.最后,列出部分初步的实验结果,分析了SDS的特点及不足.