Space and Time Hierarchies for Classes of Control Structures and Data Structures

DOI10.1145/321978.321990MaRDI QIDQ4099200zbMATH OpenOpenAlexFDO

Authors Richard J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo

Publication date 1976

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

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

Mathematics Subject Classification ID

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

Cited in

(12)

• Optimal dynamic embedding of X-trees into arrays
• Blocking for external graph searching
• The independence of control structures in abstract programming systems
• Bounds on the costs of data encodings
• Storage representations for tree-like data structures
• Bandwidth and pebbling
• Perfect Storage Representations for Families of Data Structures
• Accessibility of values as a determinant of relative complexity in algebras
• A new combinatorial approach to optimal embeddings of rectangles
• Simulations among multidimensional Turing machines
• Data encodings and their costs
• Relative complexity of algebras

This page was built for publication: Space and Time Hierarchies for Classes of Control Structures and Data Structures

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