学习加权自动机

为了扩展自动机的学习范围,提出了在理论上将加权自动机的学习能力从域扩展到有限半环的方法,在这个扩展的基础上,提出了一种基于精确学习模型的学习算法。针对该算法分析得出并不高于已有学习算法的时间复杂度,基于扩展了的定义域给出可以学习的实例,通过实验给出了一套对比学习确定加权自动机算法的实验结果,对状态缩减程度进行了说明和分析,阐述了该算法的正确完备性和更广的适用范围。

几类带空转移的n元伪加权自动机的关系

引入了n元伪加权有穷自动机——带有n个有限字符集的伪加权有穷自动机、分明型n元伪加权有穷自动机和确定型n元伪加权有穷自动机的概念。根据状态转移函数在每个字符集上是否带空转移,将以上自动机分为4类:带r-型空转移的n元伪加权有穷自动机和带空转移的n元伪加权有穷自动机和带r-型空转移的分明型n元伪加权有穷自动机和带空转移的分明型n元伪加权有穷自动机。给出了以上自动机所识别语言的定义并探究了它们之间的关系,讨论了状态转移函数在每个字符集上是否带空转移对其接受语言的影响。

加权自动机的极小确定化

本文给出了可消d-半环上加权自动机的极小确定化算法及其证明。通过定义加权自动机的等价状态,利用状态集上的等价关系和极大分解给出了可消d-半环上加权自动机的完备极小确定化算法,并给出了该算法的详细证明。

状态转移函数对加权自动机计算能力的影响

在非确定型加权自动机(NS-WA)与确定型加权自动机(DS-WA)的基础上,引入了状态转移函数是分明的非确定型加权自动机(NS-WAc)与状态转移函数是分明的带空移动的非确定型加权自动机(NS-WAε-c)的概念。在已知NS-WA与DS-WA不等价的结论下,进一步探究了NS-WAc、NS-WAε-c与DS-WA之间的等价性,并给出了等价性证明以及相关的算法和例子。

加权有限自动机的幺半群

讨论了加权有限自动机的变换幺半群,并通过加权有限自动机的同余关系,提出了语法幺半群的概念,给出了语法幺半群有限的条件,并建立了变换幺半群与语法幺半群之间的关系。最后讨论了加权有限自动机的转移幺半群。

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

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

取值于赋值幺半群的加权下推自动机的代数性质

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

加权有穷自动机的代数性质

在加权有穷自动机理论基础上,利用强同态的概念,证明两个加权有穷自动机在计算能力上是等价的,并在加权有穷自动机的状态集上建立一种等价关系,得到加权有穷自动机的商自动机,证明加权有穷自动机与其商自动机在计算能力上也是等价的。并通过引入加权有穷自动机的可交换性、分离性、(强)连通性及层的概念,讨论在(强)同态的条件下,两个加权有限状态机之间的可交换性、分离性、(强)连通性及层的关系。

数字图像的加权有限自动机表示

传统的图像压缩技术JPEG方法采用小波变换、离散余弦变换等方法进行,文中所使用的方法是与JPEG技术完全不同的方法[1],在用字母表上的字表示像素地址的基础上把每个像素的地址映射为一实数,则可以得到多分辨率灰度图像的加权有限自动机表示方法,该方法的有效应用将使图像压缩[1~7]的比例得以提高.

加权有限自动机在灰度图像中的应用

将WFA(加权有限自动机)作为灰度图像的描述工具,概括了如何从输入的图像计算相应的WFA(编码)以及如何从WFA出发画出其所定义的图像(解码)。编码算法的新颖之处在于它从数学角度出发,利用的原理是状态图像的子块图像可以被自动机中状态的线性组合来表示。基于线性代数的算法更加高效简洁。

元胞自动机压缩算法仿真卫星云图

为减小计算复杂度和提高压缩比,提出基于方块编码和可逆元胞自动机结合的二值图像压缩算法来仿真卫星云图简单实用的元胞自动机编码表示方法。并针对卫星云图特性和业务实际,提出搜索和统计云图元胞邻域的状态集合,改进加权有限元胞自动机算法,对卫星云图数据进行压缩。实验表明,两种编码方法都能有效地减小计算复杂度,提高压缩比。峰值信噪比(PSNR)在30 dB左右,RCA-BTC算法压缩率可以达到15,图像重建仿真效果良好。

取值于赋值幺半群的加权正则文法语言

正则文法是研究自动机的重要工具。引入取值于赋值幺半群的加权正则文法、加权类正则文法的定义,讨论了赋值幺半群上加权正则文法、加权类正则文法和加权有限自动机(WFA)的关系。证明了在赋值幺半群上,已知一个加权正则文法或加权类正则文法,分别存在一个WFA与之等价。定义了可分配的赋值幺半群,证明了在可分配的赋值幺半群上已知一个WFA,存在一个加权正则文法和加权类正则文法与之等价,即证明了可分配的赋值幺半群上加权正则文法、加权类正则文法和WFA在生成语言上等价,并举例说明了赋值幺半群的可分配性不是已知WFA存在与之等价的加权正则文法或加权类正则文法的必要条件。

加权有限自动机及其商变换半群

加权有限自动机是处理不确定环境下的计算的一种通用数学模型.文章对加权有限自动机及其乘积的结构作了进一步的研究.引入了加权变换半群和商变换半群的概念,并依据半环自身的结构,给出了加权有限自动机诱导的商变换半群有限的条件.讨论了加权有限自动机在各种乘积情形下的状态转移函数的性质,并建立了加权有限自动机的乘积(级联积)与其对应的商变换半群之间的关系,为进一步研究加权有限自动机的结构奠定了基础.

可逆加权树自动机

提出可逆自下而上树自动机,可逆加权树自动机和弱可逆加权树自动机的概念,证明了Σ和交换半环S上的可逆加权树自动机所识别语言的全体关于标量乘法、Hadamard-Product运算封闭,Σ和交换半环S上可逆加权树自动机所识别的语言做和运算得到的树语言为弱可逆树语言,Σ和交换半环S上的可逆加权树语言包含任何形式为1α的树级数(其中α为Σ(0)中任意元),Σ和半域S上的任一可逆加权树自动机与Σ和半域S上的一有布尔根权的可逆加权树自动机等价,可逆树语言的可识别性在半环同态下保持,Σ和布尔半环B上可逆加权树自动机所识别语言(即树级数)的全体构成的集合的支集与Σ上可逆自下而上树自动机所识别语言的全体构成的集合是相等关系,Σ和正半环S上可逆加权树自动机所识别语言(即树级数)的全体构成的集合的支集包含在Σ上可逆自下而上树自动机所识别语言的全体构成的集合中等性质。

一种多项式时间的路径敏感的污点分析方法

提出了一种解决静态污点分析方法在进行路径敏感的分析时面临的路径爆炸的问题的方法.该方法将污点分析问题转化为加权下推自动机的广义下推后继问题,进一步利用污点数据在程序中的可达性,减少后续分析中需要精确执行的路径数.从而该方法能够以多项式的时间复杂度实现程序状态空间遍历,并能在发现程序违反安全策略时自动生成反例路径.设计实验使用该方法对击键记录行为进行了刻画,对恶意代码程序和合法软件进行了两组分析实验,并与现有的方法进行了对比分析.实验证明本文的方法可以有效地对具有较多分支的程序进行路径敏感的污点分析。

分布式加权离散事件系统的协同可测性

针对状态转移会携带对应定量信息的分布式系统的可测性问题以加权自动机为模型,研究其协同可测性。首先对分布式加权离散事件系统的强协同可测性和弱协同可测性进行形式化;随后提出基于各分站点观察器构造协同观察器的算法,并得到分布式加权离散事件系统强协同可测性和弱协同可测性的充要条件;最后,给出协同可测性在无线传感器网络系统的一个应用实例。