The exponential storage cost of d-schemes

Abstract

Structured programming has been studied recently in the context of program schemes. It is in this setting that we wish to examine the question of the "inefficiency'; of structured programs. In particular, we study the "intrinsic size'; of structured program schemes when compared to equivalent nonstructured schemes. The notion of equivalence used is the one requiring equivalent schemes to compute the same function for each interpretation of their common operator and predicate symbols. To study the "intrinsic size'; of a structured scheme, we examine the size of a smallest equivalent structured scheme, and compare this with the size of a smallest equivalent nonstructured scheme. The general class of schemes studied in the present paper is the class of Ianov schemes, and the "structured'; schemes considered are the so-called Dijkstra schemes. The primary result is, from some points of view, a negative one: the intrinsic size of Dijkstra schemes may be exorbitant. To be precise, we construct a sequence F_{n} of Dijkstra schemes such that for each n, no smaller Dijkstra scheme is equivalent to F_{n}, and the number of edges in F_{n} grows exponentially. We then show there are weak equivalent nonstructured schemes G_{n} whose size grows only linearly.