Počet záznamů: 1
A Sharp Separation on Sublogarithmic Space Complexity Classes
- 1.0404724 - UIVT-O 20030013 RIV SK eng J - Článek v odborném periodiku
Žá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
Grant CEP: GA ČR GA201/02/1456
Výzkumný záměr: AV0Z1030915
Klíčová slova: space complexity * separation * diagonalization
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.254, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0124962
Počet záznamů: 1