Abstract | ||
---|---|---|
This paper examines the power of the shift primitive when included in a high level model operatin on unbounded integers. It is shown that in such a model a constant number of registers suffices for simulating an unbounded memory RAM of the sam instruction set. The simulation is on-line, and its cost can be bounded by O ( t α( s )), for a RAM program of running time t and space s . By multitask programming (postponing lengthy updates) it can be made close to real-time ( O (α( s )) per operation). |
Year | DOI | Venue |
---|---|---|
1995 | 10.1006/inco.1995.1026 | Information and Computation |
Keywords | Field | DocType |
shift instruction,real time | Integer,Discrete mathematics,Data structure,Instruction set,Computer science,High level model,Bounded function | Journal |
Volume | Issue | ISSN |
117 | 1 | Information and Computation |
Citations | PageRank | References |
7 | 0.66 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amir M Ben-Amram | 1 | 327 | 30.52 |
Zvi Galil | 2 | 3634 | 1426.98 |