A Sharp Separation on Sublogarithmic Space Complexity Classes

0404724 - UIVT-O 20030013 RIV SK eng J - Journal Article
Žák, Stanislav
A Sharp Separation on Sublogarithmic Space Complexity Classes.
Computing and Informatics. Roč. 21 (2003), s. 617-624. ISSN 1335-9150. E-ISSN 1335-9150
R&D Projects: GA ČR GA201/02/1456
Institutional research plan: AV0Z1030915
Keywords : space complexity * separation * diagonalization
Subject RIV: BA - General Mathematics
Impact factor: 0.254, year: 2003
http://www.cai.sk/ojs/index.php/cai/article/view/478

We present sharp separation results for sublogarithmic space complexity classes of the form: For any, arbitrarily slow growing, recursive nondecreasing and unbounded function s there is a natural k and an unary language L such that L is in SPACE(s(n)+k) but not in SPACE(s(n-1)). We use different types of so called demon (Turing) machines where the tape limit is given automatically without any construction, a very sensitive measure of space complexity of computations and succint diagonalization method.
Permanent Link: http://hdl.handle.net/11104/0124962