软件学报

作者：魏秀娟,李永明

单位：魏秀娟，陕西师范大学 数学与信息科学学院, 陕西 西安 71011911,李永明，陕西师范大学 数学与信息科学学院, 陕西 西安 710119;陕西师范大学 计算机科学学院, 陕西 西安 71011902

关键词：格值交替树自动机;格值正布尔公式;对偶运算;格值计算树;接受运行

基金：国家自然科学基金（11671244，11271237）；高等学校博士学科点专项科研基金（20130202110001）

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

来源：2019年第12期

《软件学报》期刊编辑部

查看软件学报杂志2019年第12期