Electronic Resource
Springer
Theory of computing systems
19 (1986), S. 13-28
ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Paul and Reischuk devised space efficient simulations of logarithmic cost random access machines and multidimensional Turing machines. We simplify their general space reduction technique and extend it to other computational models, including pointer machines, which model computations on graphs and data structures. Every pointer machine of time complexityT(n) can be simulated by a pointer machine of space complexityO(T(n)/logT(n)).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01704903
Permalink
|
Location |
Call Number |
Expected |
Availability |