Deterministic multitape automata computations

摘要

The purpose of this paper is to investigate the computational complexities of deterministic multistack-tape automata and deterministic multipushdown-tape automata. It is shown that if a given computation requires T(n) steps for a k-tape Turing machine, then it requires at most rT(n) log2T(n) steps for a deterministic two-stack-tape automaton, where r is a constant independent of n. Hierarchies of computational complexity classes are examined; for instance, it is shown that for any pair of real numbers (p, q) satisfying the condition 1≤p