On two-way multihead automata

摘要

For each positive integer n, let ℒN(n) be the class of sets accepted by a family of automata of type N, each with a read-only input with endmarkers and n two-way input heads. The following result, which is applicable to most types of two-way multihead devices, is proved: If for each positive integer n, there is some integer Mn>n such that ℒN(n) is properly contained in ℒN(Mn), then ℒN(n) is properly contained in ℒN(n + cN) for each n, where cN=1 or 2, depending on the type of the device. As a consequence, it is shown that deterministic two-way finite automata with n+2 heads are strictly more powerful than deterministic two-way finite automata with n heads for each positive integer n. It is also shown that the class of sets accepted by deterministic (nondeterministic) two-way pushdown automata with n heads is properly included in the class of sets accepted by deterministic (nondeterministic) two-way pushdown automata with n+1 heads.