Browse Prior Art Database

On 3-Head Versus 2-Head Finite Automata

IP.com Disclosure Number: IPCOM000128521D
Original Publication Date: 1974-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 13 page(s) / 30K

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+4]

Abstract

A. direct. proof is given that shows that (one-way) 3-head deterministic finite automata are computationally more powerful than 2-head finite automata. This research was supported by the National Science Foundation Grant GJ-3561.

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

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On 3-Head Versus 2-Head Finite Automata

Oscar H. Ibarra and Chul E. Kim

001 59 Computer, Information, and Control Sciences Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Technical Report-74-9 .?aY. 1974

-h This research vlas supported by the r3ational Science Foundation Grant GJ-35614.

Cover courtesy of Ruth and Jay Leavitt On 3--Head Versus 2-Head Finite Automata T by

Oscar H. Ibarra and Chul E. Kim Department of Computer Science University of Minnesota Minneapolis, Minnesota 5555

Abstract

A. direct. proof is given that shows that (one-way) 3-head deterministic finite automata are computationally more powerful than 2-head finite automata. This research was supported by the National Science Foundation Grant GJ-3561.

1. Introduction

It is obvious that one-way two-head finite automata can recognize languages that are not recognized by single-head finite automata. II has been conjectured that this relationship generalizes to °'k 4~ 1 heads are better than k heads for any k > 1'' . Attempts have~.~been made to prove this conjecture but, as far as we know, no formal proof is forthcoming. In fact, we know of no proof that establishes an infinite hierarchy of one-N-,ray multihead finite automata: In this paper, we show that one-way 3-head deterministic finite automata are computationally more powerful than 2-head such machines. This result has been reported earlier by Sudborough j4]. However, Sudborough's proof (see his thesis [5] for the full proof) 1 uses a complicated argument involving a complexity measure called "turn sequence" which was related to certain computations per-formed by single-tape of-line Turing machines. Here tie present a direct proof. We feel treat our technique can be extended to prove the generali-zation mentioned above although, at present, we do not have such an extension. The proof of the main result is in section 2 where a few interesting corollaries are also given. In Section 3, we consider multihearl finite automata whose heads are allowed to sense the presence of other heads on the same input position. .The "three heads better than two" result is shown to remain valid for these devices. One-way multihead finite automata have been studied in several planes in the literature (e.g. j2,3,4]). Here we give only a brief description. ,.,A one-wad k-head noadeterzninistic finite automaton (or simply k-NFA) is a device

(Equation Omitted)

where k > I is the number of input heads, K, t, and F are finite sets of stated inpuzts., ar1.1 accepting a, states, qQ in K is the Initial state, $2 (not in E) is the rights- endmarl;.er for the inputs, and d is a mapping from

University of Minnesota Page 1 Dec 31, 1974

Page 2 of 13

On 3-Head Versus 2-Head Finite Automata

(Equation Omitted)

(Equation Omitted)

into the set of all subsets o£

An input to M is a string

(Equation Omitted)

of symbols in E delimiteed on the right end by ".$" . F...