格值交替树自动机

• 作者: 李永明 魏秀娟
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 格值交替树自动机 格值正布尔公式 对偶运算 格值计算树 接受运行
• 年，卷（期）: 2019,（12）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 3605-3621
• 页数: 17页
• 分类号: TP301
• 字数: 16601字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005611

摘要

交替(树)自动机因其本身关于取补运算的简洁性及其与非确定型(树)自动机的等价性,成为自动机与模型检测领域研究的一个新方向.在格值交替自动机与经典交替树自动机概念的基础上,引入格值交替树自动机的概念,并研究了格值交替树自动机的代数封闭性和表达能力.首先,证明了对格值交替树自动机的转移函数取对偶运算,终止权重取补之后所得自动机与原自动机接受语言互补这一结论.其次,证明了格值交替树自动机关于交、并运算的封闭性.最后,讨论了格值交替树自动机和格值树自动机、格值非确定型自动机的表达能力;证明了格值交替树自动机与格值树自动机的等价性,并给出了二者相互转化的算法及其复杂度分析;同时,提供了用格值非确定型自动机来模拟格值交替树自动机的方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李永明	陕西师范大学数学与信息科学学院	165	505	12.0	16.0
5	魏秀娟	陕西师范大学数学与信息科学学院	4	14	2.0	3.0