Publication Details
Title: The Sublogarithmic Space World
Author: M. Liskiewicz and R. Reischuk
Group: ICSI Technical Reports
Date: August 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-048.pdf
Overview:
(Pages: 42) 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.
Bibliographic Information:
ICSI Technical Report TR-93-048
Bibliographic Reference:
M. Liskiewicz and R. Reischuk. The Sublogarithmic Space World. ICSI Technical Report TR-93-048, August 1993
Author: M. Liskiewicz and R. Reischuk
Group: ICSI Technical Reports
Date: August 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-048.pdf
Overview:
(Pages: 42) 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.
Bibliographic Information:
ICSI Technical Report TR-93-048
Bibliographic Reference:
M. Liskiewicz and R. Reischuk. The Sublogarithmic Space World. ICSI Technical Report TR-93-048, August 1993