Extreme time-space tradeoffs for graphs with small space requirements |
| |
| Authors: | David A. Carlson John E. Savage |
| |
| Affiliation: | Department of Computer Science, Brown University, Providence, RI 02912, U.S.A. |
| |
| Abstract: | Two new isometric array languages, called Linear Array Languages (LAL) and Extended Regular Array Languages (ERAL), are introduced. A more abundant hierarchy for isometric languages is established. We show that some properties of two-dimensional array patterns do not coincide with their one-dimensional counterparts. |
| |
| Keywords: | Pebble game straight-line algorithm time-space tradeoff storage allocation complexity theory |
| 本文献已被 ScienceDirect 等数据库收录！ |
