Space-Time Tradeoffs in Structured Programming: An Improved Combinatorial Embedding Theorem.

Abstract

Let G and G* be programs represented by directed graphs. We define a relation < or = sub S, T between G and G* that formalizes the notion of G* simulating G with S-fold loss of space efficiency and T-fold loss of time efficiency, and prove that if G < or = sub S, T G*, where G has n statements and G* is structured, then in the worst case T + log sub 2 (log sub 2 S) > or = log sub 2 (n) + 0(log sub 2(log sub 2n)). (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1978
Accession Number
ADA062495

Entities

People

  • Richard A. Demillo
  • Richard J. Lipton
  • Stanley C. Eisenstat

Organizations

  • Georgia Tech

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Boundaries
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Efficiency
  • Embedding
  • Inequalities
  • Language
  • Military Research
  • Schools
  • Simulations
  • Simulators
  • Structured Programming
  • Trees (Data Structures)

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Computer Networking
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space