Browse Prior Art Database

On eliminating nondeterminism from Turing machines which use less than logarithm worktape space

IP.com Disclosure Number: IPCOM000128152D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 19 page(s) / 47K

Publishing Venue

Software Patent Institute

Related People

Burkhard Monien: AUTHOR [+4]

Abstract

A family of problems [Equation ommitted] is described that is log space complete [Equation ommitted] for functions S(n) which grow less rapidly than the logarithm function. An algorithm is described to recognize [Equation ommitted] deterministic- ally in space [Equation ommitted] . Thus, we show for constructible functions [Equation ommitted] that:

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

Page 1 of 19

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On eliminating nondeterminism from Turing machines which use less than logarithm worktape space

Burkhard Monien (l) and Ivan Hal Sudborough (2)

is Mo. -77 -01 - Fe, - 01

(1) Fachbereich 17 (2) E. E./C.S. Dept. Gesamthochschule Paderborn Northwestern University

4790 Paderborn Evanston, Illinois 60201 West Germany U.S.A.

the work of this author was supported in part by NSF Grant No. MCS 77-02494 and was performed in part while visiting the Gesamthochschule Paderborn in Paderborn, Germany.

Abstract

A family of problems

(Equation Omitted)

is described that is log space complete

(Equation Omitted)

for functions S(n) which grow less rapidly than the logarithm function. An algorithm is described to recognize

(Equation Omitted)

deterministic- ally in space

(Equation Omitted)

. Thus, we show for constructible functions

(Equation Omitted)

that:

(Equation Omitted)

In particular, when

(Equation Omitted)

we have:

(Equation Omitted)

Northwestern University Page 1 Dec 31, 1979

Page 2 of 19

On eliminating nondeterminism from Turing machines which use less than logarithm worktape space

In addition, it is shown that the question of whether NSPACE(S(n)) is identical to DSPACE(S(n)), for sub-logarithmic functions S(n), is closely related to the space complexity of the graph accessibility problem for graphs with bounded bandwidth. Let S(n) be a function on the natural numbers. A family of graphs

(Equation Omitted)

has bandwidth S(n), if each graph G i in the family has bandwidth S(IV 1), where V is the set of' vertices of G It is, of course, i i i* true that the family of all finite graphs has bandwidth I(n), where I(n) is the identity function.

We shall need to fix on some convenient encoding of finite directed graphs. Let

(Equation Omitted)

be such a graph, where

(Equation Omitted)

for some k ;-* 1. We shall actually not settle onjust one encoding; instead, we shall describe two separate encodings. The long encoding of G, denoted by x G , is the string:

(Equation Omitted)

where bin(j) denotes the binary representation of the integer j (with no leading zeroes), and, for

(Equation Omitted)

That is, (1) there is a block for each node in G (a "block" is a string of the form

(Equation Omitted)

where x i is a string of O's and 11s, for (2),each block begins with the number of the node in the graph it corres-ponds to, and (3) the numbers following the first number i in block i in-dicate how much needs to be added to i to get the numbers of nodes to which an edge enters from node i (these numbers can be positive or negative).

A short encoding,of G, denoted by :Wd , is a string identical to that described above for the long encoding of G except that the first number .in each block is deleted. That is, the i-th block in :

(Equation Omitted)

'Definition 1.1. Let S(n) denote any function on the natural numbers.

(Equation Omitted)

denotes the set of all long encodings of graphs

(Equation Omitted)

N...