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

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

摘要: 本文提出了一类交替的ω－有穷自动机，即所有状态都是万能的交替的ω－有穷自动机（记为ω－ＵＡＦＡ），并采用了构造的方法证明了ω－ＵＡＦＡ和确定的ω－有穷自动机在四种接受条件下接受的ω－语言的等价性。

Abstract: 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.