Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game

DOI10.1145/322217.322233zbMath0468.68068OpenAlexW1965426100MaRDI QIDQ5904874

K. Ruediger Reischuk

Publication date: 1980

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322217.322233

zbMATH Keywords

register allocationstraight-line programTuring machine computationsspace boundspebble game on directed acyclic graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Space-time tradeoffs for linear recursion

This page was built for publication: Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game