一类交替的ω－有穷自动机和确定的ω－有穷自动机识别能力的等价性  

THE EQUIVALENCE OF RECOGNIZING POWER FOR ONE TYPE OF ALTERNATING ω-FINITE AUTOMATA AND DETERMINISTIC ω-FINITE AUTOMATA

作　　者：周清雷[1] 苏锦祥[1] 

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

出　　处：《计算机研究与发展》1995年第9期17-20,26,共5页Journal of Computer Research and Development

基　　金：国家自然科学基金

摘　　要：本文提出了一类交替的ω－有穷自动机，即所有状态都是万能的交替的ω－有穷自动机（记为ω－ＵＡＦＡ），并采用了构造的方法证明了ω－ＵＡＦＡ和确定的ω－有穷自动机在四种接受条件下接受的ω－语言的等价性。In this paper, one type of alternating ω-finite automata (abbreviated ω-UAFA),that is, all states of alternating ω-finite automata are universal, is suggested. And by adopting the constructing method, it is shown that the ω-language class accepted by ω-UAFA is equal to the one accepted by deterministic ω-finite automata under four types of acceptance conditions.

关 键 词：有穷自动机 Ω-语言 自动机 识别 

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