ALTERNATION
ALTERNATION
复制标题
DOI：
10.1145/322234.322243
复制
发表时间：
1981-01-01
影响因子：
2.5
通讯作者：
STOCKMEYER, LJ
中科院分区：
文献类型：
--
作者：
CHANDRA, AK;KOZEN, DC;STOCKMEYER, LJ
交替（英语：Alternation）是非决定论的一种推广，其中存在量词和全称量词可以在计算过程中交替，而在非决定论计算中只有存在量词。交替图灵机的定义和接受精确的递归可重复集。时间（空间）有界交替图灵机所接受的语言的复杂性类的特征在于空间（时间）有界确定性图灵机所接受的语言的复杂性类。特别地，交替多项式时间等价于确定性多项式空间，交替多项式空间等价于确定性指数时间。次递归量词层次定义的时间或空间有界的交替Tufing机的限制在计算过程中允许的交替的数量。交替有限状态自动机的定义和只接受正规语言，虽然，在一般情况下，2 - 2状态是必要的，足以模拟一个k-状态交替有限自动机确定性。最后，它表明，交替下推自动机是严格更强大的非确定性下推自动机。
Alternation is a generalization of nondeterminism in which existential and universal quantitiers can alternate during the course of a computation, whereas in a nondeterministic computation there are only existential quantifiers. Alternating Turing machines are defined and shown to accept precisely the recursively enumerable sets. Complexity classes of languages accepted by time-(space-) bounded alternating Turing machines are characterized in terms of complexity classes of languages accepted by space-(time-) bounded deterministic Turing machines. In particular, alternating polynomial time is equivalent to deterministic polynomial space and alternating polynomial space is equivalent to deterministic'exponential time. Subrecursive quantifier hierarchies are defined in terms of time-or space-bounded alternating Tufing machines by bounding the number of alternations allowed during computations. Alternating finite-state automata are defined and shown to accept only regular languages, although, in general, 2 2 states are necessary and sufficient to simulate a k-state alternating finite automaton deterministically. Finally, it is shown that alternating pushdown automata are strictly more powerful than nondeterministic pushdown automata.