Tree-Size Bounded Alternation

The size of an accepting computation tree of an alternating Turing machine (ATM) is introduced as a complexity measure. Tree-size on ATM's is shown to closely correspond to time on nondeterministic TM's and on nondeterministic auxiliary pushdown automata. The later gives a useful new characterization of the class of languages log-space-reducible to context-free languages. Relationships with parallel-time complexity are also explored. ATM computations using at most space S(n) and tree-size Z(n) (simultaneously) can be simulated in alternating time S(n).log Z(n). Several well-known simulations, e.g., Savitch's theorem, are special cases of this result. It also leads to improved parallel-time bounds for many problems, e.g., context-free language recognition in time 0(log 2 n) on several parallel models.

Authors

• Walter L. Ruzzo

Keywords

No keywords are indexed for this paper.