Turing machines with sublogarithmic space /
Guardat en:
| Autor principal: | |
|---|---|
| Format: | Llibre |
| Idioma: | English |
| Publicat: |
Berlin ; New York :
Springer-Verlag,
c1994.
|
| Col·lecció: | Lecture notes in computer science ;
843. |
| Matèries: |
Taula de continguts:
- 1. Introduction
- 2. Basic Notions
- 3. Languages Acceptable with Logarithmic Space
- 4. Examples of Languages Acceptable with Sublogarithmic Space
- 5. Lower Bounds for Accepting Non-regular Languages
- 6. Space Constructible Functions
- 7. Halting Property and Closure under Complement
- 8. Strong versus Weak Mode of Space Complexity
- 9. Padding
- 10. Deterministic versus Nondeterministic Turing Machines
- 11. Space Hierarchy
- 12. Closure under Concatenation
- 13. Alternating Hierarchy
- 14. Independent Complement
- 15. Other Models of Turing Machines.