期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
