Space-time tradeoffs for linear recursion

DOI10.1007/BF01744566MaRDI QIDQ3968456zbMATH OpenOpenAlexFDO

Authors Sowmitri Swamy, John Savage

Publication date 1983

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01744566

zbMATH Keywords

pebbling of a simple graph

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A Time-Space Trade-Off
• scientific article; zbMATH DE number 3614810 (Why is no real title available?)
• scientific article; zbMATH DE number 3622921 (Why is no real title available?)
• scientific article; zbMATH DE number 3628386 (Why is no real title available?)
• scientific article; zbMATH DE number 3316587 (Why is no real title available?)
• Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game
• On Time Versus Space
• Space bounds for a game on graphs
• Space-time trade-offs on the FFT algorithm
• Time-space trade-offs in a pebble game
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits

Cited in

(3)

• Nullstellensatz size-degree trade-offs from reversible pebbling
• On Reducing the Space Requirements of a Straight-Line Algorithm
• Nullstellensatz size-degree trade-offs from reversible pebbling

This page was built for publication: Space-time tradeoffs for linear recursion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3968456)