基于超线性时序逻辑的无二义加权自动机的可检测性研究

1

作者 张涛 彭皓天 《天津理工大学学报》 2025年第1期112-117,共6页

文中从超线性时序逻辑(hyper linear temporal logic, HyperLTL)的角度深入探讨了加权离散事件系统(discrete event systems, DESs)的可检测性问题。先前关于DESs的研究通常假设事件转换是瞬时的或无需成本的。然而,在实际生产环境中,... 文中从超线性时序逻辑(hyper linear temporal logic, HyperLTL)的角度深入探讨了加权离散事件系统(discrete event systems, DESs)的可检测性问题。先前关于DESs的研究通常假设事件转换是瞬时的或无需成本的。然而,在实际生产环境中,事件转换往往涉及时间和成本的消耗,这需要在DESs研究中引入加权因素。加权决策策略旨在通过为不同事件或状态分配权重来优化系统性能、指导政策制定,并实现高效、安全和可靠地运行。讨论了从加权DESs建模中得出的无二义加权自动机(unambiguous weighted automata, UWAs)。在此基础上,将其转换为一种特殊的Kripke结构,以捕获此类加权自动机的信息,从而实现HyperLTL的明确表示。 展开更多

关键词 网络安全 离散事件系统 可检测性 超线性时序逻辑 无二义加权自动机

在线阅读 下载PDF 职称材料

加权自动机的极小确定化 被引量：1

2

作者 庞美玲 李永明 《模糊系统与数学》 CSCD 北大核心 2015年第6期124-137,共14页

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

关键词 可消d-半环 加权自动机 完备极小确定化 完备极小化算法

原文传递

状态转移函数对加权自动机计算能力的影响 被引量：2

3

作者 赵路瑶 王海辉 李平 《模糊系统与数学》 北大核心 2020年第3期127-133,共7页

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

关键词 半环 加权自动机 状态转移函数 空转移 等价性

原文传递

学习加权自动机

4

作者 惠涵 贺飞 顾明 《计算机工程与设计》 CSCD 北大核心 2014年第6期1962-1967,共6页

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

关键词 学习算法 加权自动机 量化语言 域 有限半环

在线阅读 下载PDF 职称材料

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

5

作者 赵路瑶 王海辉 李平 《计算机工程与科学》 CSCD 北大核心 2022年第2期364-371,共8页

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

关键词 伪半环 n元伪加权有穷自动机 状态转移函数 空转移 关系

在线阅读 下载PDF 职称材料

加权有限自动机的幺半群 被引量：2

6

作者 王拥兵 李永明 《陕西师范大学学报（自然科学版）》 CAS CSCD 北大核心 2016年第5期21-25,共5页

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

关键词 半环 加权有限自动机 局部有限 同态

在线阅读 下载PDF 职称材料

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

7

作者 汪国武 《计算机应用与软件》 CSCD 2016年第8期23-26,87,共5页

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

关键词 量化等价 不确定的有限状态自动机 加权自动机 形式化验证

在线阅读 下载PDF 职称材料

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

8

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

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

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

在线阅读 下载PDF 职称材料

加权有穷自动机的代数性质 被引量：3

9

作者 张丽霞 《计算机工程与科学》 CSCD 北大核心 2014年第11期2186-2190,共5页

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

关键词 形式幂级数 加权有穷自动机 同态 强连通

在线阅读 下载PDF 职称材料

数字图像的加权有限自动机表示 被引量：1

10

作者 刘跃霞 刘耀军 阎金瑶 《太原师范学院学报（自然科学版）》 2010年第2期52-55,73,共5页

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

关键词 加权有限自动机 像素 状态图像 转移矩阵

在线阅读 下载PDF 职称材料

可逆加权树自动机

11

作者 魏秀娟 李永明 《模糊系统与数学》 CSCD 北大核心 2015年第4期125-134,共10页

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

关键词 可逆自动机 加权树自动机 Σ-代数 树级数

原文传递

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

12

作者 孟青慧 刘耀军 《电脑开发与应用》 2011年第2期22-24,共3页

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

关键词 WFA(加权有限自动机) 多分辨率图像 线性表示

在线阅读 下载PDF 职称材料

元胞自动机压缩算法仿真卫星云图 被引量：1

13

作者 邹阳 王将 +2 位作者 张昭晖 刘祎 梁立为 《计算机应用与软件》 北大核心 2018年第4期265-268,302,共5页

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

关键词 方块编码 可逆元胞自动机 加权有限元胞自动机 卫星云图仿真 数据压缩

在线阅读 下载PDF 职称材料

取值于赋值幺半群的加权正则文法语言 被引量：1

14

作者 赵菲 李永明 《计算机工程与科学》 CSCD 北大核心 2016年第7期1405-1412,共8页

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

关键词 赋值幺半群 加权正则文法 加权自动机

在线阅读 下载PDF 职称材料

加权有限自动机及其商变换半群 被引量：1

15

作者 王拥兵 《系统科学与数学》 CSCD 北大核心 2016年第10期1610-1617,共8页

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

关键词 半环 局部有限 加权有限自动机 乘积 级联积

原文传递

一种多项式时间的路径敏感的污点分析方法 被引量：4

16

作者 李佳静 王铁磊 +2 位作者 韦韬 凤旺森 邹维 《计算机学报》 EI CSCD 北大核心 2009年第9期1845-1855,共11页

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

关键词 加权下推自动机 数据流分析 污点分析 恶意行为 击键记录

在线阅读 下载PDF 职称材料

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

17

作者 郑恒 刘富春 蒋艳荣 《信息与控制》 CSCD 北大核心 2023年第4期525-530,541,共7页

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

关键词 离散事件系统 加权自动机 分布式系统 协同可测性

原文传递