Browse Prior Art Database

On Two-way Multihead Automata

IP.com Disclosure Number: IPCOM000128504D
Original Publication Date: 1971-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 11 page(s) / 28K

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+3]

Abstract

For each positive integer [Equation ommitted] be the class of sets accepted by a family of automata of type N, each with a read-only i nput 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 H I > n such that (n) is properly contained in [Equation ommitted] then (n) is properly contained [Equation ommitted] for each n, where [Equation ommitted] , 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+l heads.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On Two-way Multihead Automata

by

Oscar H. Ibarra

Department of Computer Science

Institute of Technology University of Minnesota Minneapolis, Minnesota December, 1971

Abstract

For each positive integer

(Equation Omitted)

be the class of sets accepted by a family of automata of type N, each with a read-only i nput 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 H I > n such that (n) is properly contained in

(Equation Omitted)

then (n) is properly contained

(Equation Omitted)

for each n, where

(Equation Omitted)

, 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+l heads.

Introduction

For most types of two-way multihead automata with read-only inputs with endmarkers, one can often show that for each positive integer n, there is some integer M n > n such that automata with M n input heads are strictly more powerful than those with n heads. Usually, a diagonal argument of some sort can be used to establish such a result. For example, a straightforward diagonal met-hod would show that for every positive integer-n,there is some integer M n > n such that the class of sets accepted by deterministic two-way finite-automata with n heads is

University of Minnesota Page 1 Dec 31, 1971

Page 2 of 11

On Two-way Multihead Automata

properly included in the class of sets accepted by deterministic two- way finite automata with M heads. However, the diagonalization technique seems n to apply only if we assume that

(Equation Omitted)

. Thus, although we get a hierarchy of classes of sets accepted by deterministic two-way, multihead finite automata, we are still left with-large gaps between any two, classes. In this paper, we offer a result which is useful in refining hierarchies of classes of acceptable sets for two-way multihead devices. We use this .result to show that deterministic two-way finite automata with u+2 heads are strictly more powerful than deterministic two-way finite automata with n heads for every positive integer n. We also show 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 such machines with M-1 heads.

For most types of two-way multihead automata with read-only inputs with endmarkers, one can often show that for each positive integer n, there is some integer M n > n such that automata with...