Complete Register Allocation Problems

DOI10.1137/0204020zbMath0327.68042MaRDI 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

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68N01: General topics in the theory of software

68W99: Algorithms in computer science

Related Items

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