TR95-005 Authors: Maciej Liskiewicz, RĂ¼diger Reischuk

Publication: 1st January 1995 00:00

Downloads: 966

Keywords:

This paper tries to fully characterize the properties and relationships

of space classes defined by Turing machines that use less than

logarithmic space - may they be deterministic,

nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages and show that

such machines are unable to accept these languages.

The basic proof method is a nontrivial extension of the

1^n --> 1^{n+n!} technique to alternating TMs.

Let llog denote the logarithmic function iterated twice, and

Sigma_k-Space(S), Pi_k-Space(S)

be the complexity classes defined by S-space-bounded ATMs

that alternate at most k-1 times and start in an existential, resp.

universal state. Our first result shows that for each k > 1 the sets

Sigma_k-Space(llog) \ Pi_k-Space(o(log)) and

Pi_k-Space(llog) \ Sigma_k-Space(o(log))

are both not empty.

This implies that for each S between llog and o(log) the classes

Sigma_1-Space(S), Sigma_2-Space(S), Sigma_3-Space(S),

form an infinite hierarchy.

Furthermore, this separation is extended to space classes defined

by ATMs with a nonconstant alternation bound A provided that

the product A * S grows sublogarithmically.

These lower bounds can also be used to show that basic closure

properties do not hold for such classes. We obtain

that for any S between llog and o(log) and all k > 1

Sigma_k-Space(S) and Pi_k-Space(S) are not

closed under complementation and concatenation.

Moreover, Sigma_k-Space(S) is not closed under intersection,

and Pi_k-Space(S) is not closed under union.

It is also shown that ATMs recognizing bounded languages can

always be guaranteed to halt. For the class of Z-bounded languages

with Z less than exp S we obtain the equality

co-Sigma_k-Space(S) = Pi_k-Space(S) .

Finally, for sublogarithmic bounded ATMs we give a separation

between the weak and the strong space measure,

and prove a logarithmic lower space bound for the recognition of

nonregular context-free languages.