论文摘要
交替(树)自动机因其本身关于取补运算的简洁性及其与非确定型(树)自动机的等价性,成为自动机与模型检测领域研究的一个新方向.在格值交替自动机与经典交替树自动机概念的基础上,引入格值交替树自动机的概念,并研究了格值交替树自动机的代数封闭性和表达能力.首先,证明了对格值交替树自动机的转移函数取对偶运算,终止权重取补之后所得自动机与原自动机接受语言互补这一结论.其次,证明了格值交替树自动机关于交、并运算的封闭性.最后,讨论了格值交替树自动机和格值树自动机、格值非确定型自动机的表达能力;证明了格值交替树自动机与格值树自动机的等价性,并给出了二者相互转化的算法及其复杂度分析;同时,提供了用格值非确定型自动机来模拟格值交替树自动机的方法.
论文目录
文章来源
类型: 期刊论文
作者: 魏秀娟,李永明
关键词: 格值交替树自动机,格值正布尔公式,对偶运算,格值计算树,接受运行
来源: 软件学报 2019年12期
年度: 2019
分类: 信息科技
专业: 计算机软件及计算机应用
单位: 陕西师范大学数学与信息科学学院,陕西师范大学计算机科学学院
基金: 国家自然科学基金(11671244,11271237),高等学校博士学科点专项科研基金(20130202110001)~~
分类号: TP301.1
DOI: 10.13328/j.cnki.jos.005611
页码: 3605-3621
总页数: 17
文件大小: 743K
下载量: 25
相关论文文献
- [1].欧洲自动机艺术的兴盛与衰败[J]. 新美术 2019(12)
- [2].某导气式火炮自动机身管磨损后的性能分析[J]. 兵器装备工程学报 2020(08)
- [3].某高速自动机冷却系统分析[J]. 机械制造与自动化 2017(02)
- [4].量子自动机的交换性[J]. 计算机工程与应用 2016(20)
- [5].自动机终结字查找算法的设计与实现[J]. 计算机科学 2020(S2)
- [6].自动机凸轮曲线动力学性能改进[J]. 兵器装备工程学报 2020(09)
- [7].基于虚拟样机技术对手枪新型自动机的研究[J]. 河北农机 2016(03)
- [8].树自动机超最小化[J]. 南昌航空大学学报(自然科学版) 2015(02)
- [9].确定权重有限自动机的同余及极小自动机[J]. 纯粹数学与应用数学 2015(05)
- [10].可逆加权树自动机[J]. 模糊系统与数学 2015(04)
- [11].高射频武器自动机测试实验研究及分析[J]. 中北大学学报(自然科学版) 2012(06)
- [12].高射速自动机后坐力控制[J]. 火炮发射与控制学报 2011(02)
- [13].基于模糊物元的舰炮自动机性能评价[J]. 舰船电子工程 2009(07)
- [14].一类同步自动机及损耗函数分析[J]. 计算机科学 2019(S2)
- [15].一种自治操作条件反射自动机[J]. 控制理论与应用 2012(11)
- [16].基于分形理论的高速自动机故障诊断[J]. 机械工程与自动化 2014(02)
- [17].学习加权自动机[J]. 计算机工程与设计 2014(06)
- [18].火炮自动机故障诊断研究综述[J]. 机械管理开发 2013(01)
- [19].外能源转管自动机机电耦合动力学键合图建模及应用[J]. 火炮发射与控制学报 2013(01)
- [20].基于混成自动机的车联网服务建模方法[J]. 南通大学学报(自然科学版) 2013(02)
- [21].改进的八近邻区域边界标定自动机[J]. 华东师范大学学报(自然科学版) 2009(01)
- [22].模糊自动机的强连通性及群自动机[J]. 纯粹数学与应用数学 2009(03)
- [23].单模式串匹配自动机的设计与实现[J]. 南通职业大学学报 2008(01)
- [24].基于分时段规范变量残差分析的高速自动机动态特性监测[J]. 振动与冲击 2019(20)
- [25].有关本原自动机的研究[J]. 空军工程大学学报(自然科学版) 2016(02)
- [26].使用事件自动机规约的C语言有界模型检测[J]. 软件学报 2014(11)
- [27].某转管自动机停射故障分析[J]. 火炮发射与控制学报 2014(04)
- [28].基于场景自动机的网构软件演化[J]. 计算机科学 2014(11)
- [29].多模式匹配自动机的构造与极小化[J]. 铜仁学院学报 2011(03)
- [30].状态转移函数对加权自动机计算能力的影响[J]. 模糊系统与数学 2020(03)
标签：格值交替树自动机论文; 格值正布尔公式论文; 对偶运算论文; 格值计算树论文; 接受运行论文;