Please use this identifier to cite or link to this item: doi:10.22028/D291-26082
Title: The exponential storage cost of d-schemes
Author(s): Tindell, Ralph
Language: English
Year of Publication: 1976
OPUS Source: Saarbrücken, 1976
DDC notations: 004 Computer science, internet
Publikation type: Report
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.
Link to this record: urn:nbn:de:bsz:291-scidok-40382
Series name: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Series volume: 1976/10
Date of registration: 27-Jul-2011
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14_1976_10.pdf3,15 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.