格值交替树自动机

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