Complete Register Allocation Problems

DOI10.1137/0204020zbMath0327.68042OpenAlexW2056304107MaRDI QIDQ4092979

Ravi Sethi

Publication date: 1975

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0204020

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items (31)

Bounded MSC communication ⋮ Static-memory-hard functions, and modeling the cost of space vs. time ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Optimal contiguous expression DAG evaluations ⋮ Proof of Space from Stacked Expanders ⋮ Memory management optimization problems for integrated circuit simulators ⋮ Min Cut is NP-complete for edge weighted trees ⋮ Reversible Pebble Game on Trees ⋮ Pebbling meets coloring: reversible pebble game on trees ⋮ Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks ⋮ Typical sequences revisited -- computing width parameters of graphs ⋮ Pebble games for studying storage sharing ⋮ On the cost of recomputing: tight bounds on pebbling with faults ⋮ Scanning Phylogenetic Networks Is NP-hard ⋮ The complexity of minimum-length path decompositions ⋮ A higher-order strategy for eliminating common subexpressions ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ The project scheduling problem with production and consumption of resources: a list-scheduling based algorithm ⋮ Storage requirements for deterministic polynomial time recognizable languages ⋮ Memory-optimal evaluation of expression trees involving large objects ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Time-space trade-offs in a pebble game ⋮ A polynomial algorithm for minDSC on a subclass of series Parallel graphs ⋮ More general parallel tree contraction: Register allocation and broadcasting in a tree ⋮ Global storage cells for attributes in an attribute grammar ⋮ Searching and pebbling ⋮ Optimal memory-aware backpropagation of deep join networks ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ On the cost of recomputing: Tight bounds on pebbling with faults ⋮ Bandwidth and pebbling ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling

This page was built for publication: Complete Register Allocation Problems