Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A Note Concerning Nondeterministic Tape Complexities

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

Publishing Venue

Software Patent Institute

Related People

Oscar H. Iberre: AUTHOR [+3]

Abstract

A set of sufficient conditions on tape functions.[Equation ommitted] is presented that guarantees the existence of a set accepted by an L (n)-tape bounded nondeterministic Turing machine but not accepted by any L 2 (n)-tape bounded nondeterministic Turing machine. Interesting corollaries arise. For example, it is 'shown that for Integers [Equation ommitted] there is a [Equation ommitted] set decepted by an (n , ]-tape bounded nondeterministic Turing.machine that is not accepted by any [Equation ommitted] tape bounded nondeterministic Turing machine.

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

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Note Concerning Nondeterministic Tape Complexities

by Oscar H. Iberre

Technical Report 71-3 December, 1971

Abstract

A set of sufficient conditions on tape functions.

(Equation Omitted)

is presented that guarantees the existence of a set accepted by an L (n)-tape bounded nondeterministic Turing machine but not accepted by any L 2 (n)-tape bounded nondeterministic Turing machine. Interesting corollaries arise. For example, it is 'shown that for Integers

(Equation Omitted)

there is a

(Equation Omitted)

set decepted by an (n , ]-tape bounded nondeterministic Turing.machine that is not accepted by any

(Equation Omitted)

tape bounded nondeterministic Turing machine.

Introduction

Hartmaids, Lewis, and Stearns (3] have shown that for any tape functions,

(Equation Omitted)

with

(Equation Omitted)

full . y constructable and

(Equation Omitted)

there is a set accepted by an L 1 (n)-tape bounded deterministic Turing ,machine, but not accepted by any L 2 (n)~tape bounded deterministic Turing machine. This result, however, does not.seem.to generalize for nondeterministic Turing machines. The result of Savitch (9),

University of Minnesota Page 1 Dec 31, 1971

Page 2 of 10

A Note Concerning Nondeterministic Tape Complexities

which'states that for any tape function L(n) I (log2n] a set accepted. by an L(n)-tape bounded nondeterministic Turing machine is-alsqa accepted by an (L(n)) 2_ tape bounded deterministic Turing machine,.can be used'in conjunction-wi.th the.result above to show that some nondeterministic tape complexity~classes properly contain other-tape complexity classes. For example, lt-follows that there exists a set

3 accepted by an.n -tape bounded nondeterministic Turing,.machine that is accepted by no n- tape bounded nondeterministIc Turing machine. However, the

(Equation Omitted)

argument fails for nondeterministic tape bounds like L (n) - n and L (n)- n 1 2~ In this paper, we derive a set of sufficient conditions on tape functions L (n) and L (n) that insures the existence of a set accepted by an L (n)-tape 1 2 bounded nondeterministic Turing machine but not accepted by any L 2 (n)-tape bounded nondeterministic Turing.machine. We use these conditions to show, for example, that f or integers,

(Equation Omitted)

, there is a set accepted by an [n M+(p/q) ]-tape b I ounded nondeterministic Turing machine that is not accepted

(Equation Omitted)

tape I bounded nondeterministic Turing . machine. It follows from this result and the fact that a two-way nondeterministic nonerasing stack automaton is~equivalent to an n 2_ tape bounded nondeterministic

-2-

Turing machine 151 that there is a non-co . ntext-sensitive language that is accepted by, a two- way nondeterministic nonerasing stack automaton, answering a problem posed-An [2j. 'lie also show that an (m+l)-head two-way nondeterministic nonerasing.s.tack automaton [7] (respectively,.(rr~l)-hea4 two-way nondetermi n-' istic ch...