Research Catalog
Turing machines with sublogarithmic space
- Title
- Turing machines with sublogarithmic space / Andrzej Szepietowski.
- Author
- Szepietowski, Andrzej.
- Publication
- Berlin ; New York : Springer-Verlag, [1994], ©1994.
Items in the Library & Off-site
Filter by
1 Item
| Status | Format | Access | Call Number | Item Location |
|---|---|---|---|---|
| Text | Request in advance | QA267 .S987 1994 | Off-site |
Holdings
Details
- Description
- viii, 114 pages; 23 cm.
- Series Statement
- Lecture notes in computer science ; 843
- Uniform Title
- Lecture notes in computer science ; 843.
- Subjects
- Bibliography (note)
- Includes bibliographical references and indexes.
- Contents
- 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.
- ISBN
- 0387583556
- LCCN
- 94030238
- OCLC
- ocm30893802
- Owning Institutions
- Columbia University Libraries