On two-way multihead automata

✍ Scribed by Oscar H. Ibarra

• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 479 KB
• Volume: 7
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(73)80048-0

✦ Synopsis

For each positive integer n, let -~eN(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 M~ > n such that -o~~ is properly contained in -~aN(Mn), then ~N(n) is properly contained in 9 LPN(n + CN) for each n, where c N = 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 + I heads.