Space-Time Trade-Offs in Structured Programming
Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton · Journal of the ACM · 1980
AnSTRACT Let G and G* be programs represented by directed graphs There is defined a relation ~-s.r between G and G* that formahzes the notton of G* simulating G with Sffold loss of space efficiency and T-fold loss of time efficiency, ~t is proved that ff G - lo B n + O(Iog2 logz n) KEY WORDS AND PHRASES ancestor tree, complexity, control structure, dtrected graph, embedding CR CATEGORIES 4 22, 4 34, 5 24, 5 32 IntroducttonIn a previous paper [1] we made precise some intuitwe observations concerning the efficiency of structured programs by defining a combinatorial relation that corresponds to the notion of uniform szrnulatton between programs.Informally, we say that a program G* uniformly simulates a program G ff G* carries out the computation of G (and possibly addRlonal computation which might be regarded as "bookkeeping") in such a way that the space-time efficiency of G is degraded by a factor that is independent of the size of G.The main results of [ 1] indicate that the nonexistence of uniform simulations among many well-known classes of control structures is at least in part due to the combinatorial aspects of program structure and not to such details of program orgamzation as choice of data structures or limitations on the form of Boolean expressions.Indeed, the main result of [1, Th. 5.1] provides a nontrivml lower bound on the loss of space-time efficiency in any structured simulation of a goto program.This short note extends that result, improving the space-time inequality of [1, Th. 5.1] by an exponentml.Thus we now show that there are goto programs with n statements such that for any structured simulation either Pernnsslon to copy wtthout fee all or part of this matenal is granted provided that the copies are not made or distnbuted for direct commercial advantage, the ACM copyright notice and the tttle of the pubhcation and Rs date appear, and notice is gwen that copying ts by permission of the AssoclaUon for Computing Machinery To copy otherwise, or to republish, requires a fee and/or specific permission These results were announced at the 1976 Johns Hopkins Conference on Information Sciences and Systems