交替ω有穷自动机接受ω语言能力的研究  

Study on Power of Alternating ω Automata Accepting ω Language

作　　者：周清雷[1] 周文俊[1] 

机构地区：[1]郑州大学计算机科学系,郑州450052

出　　处：《郑州大学学报（自然科学版）》1999年第3期23-27,共5页Journal of Zhengzhou University (Natural Science)

基　　金：国家自然科学基金

摘　　要：本文研究了交替ω有穷自动机关于接受条件 Ｚ１ 和 Ｚ２ 接受ω语言的能力，并且与交替ω有穷自动机关于另外接受条件接受ω语言的能力进行了比较，从而得出了下面主要结果： Ａ Ｃ１  Ａ Ｚ１ ＝ Ａ Ｓ Ｚ１ ＝ Ａ Ｓ Ｚ２  ＡThe power that alternating ω automata accepts ω language with respect to Z 1 or Z 2 are studied. This power is compared with the power that alternating ω automata accepts ω language with respect to the others accepting conditions. Therefor, the main results are obtained:A C 1 A Z 1 =A S Z 1 =A S Z 2 A Z 2 .

关 键 词：Ω-有穷自动机 接受条件 Ω-语言 自动机 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构] TP23[自动化与计算机技术—计算机科学与技术]