Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26082
Titel: The exponential storage cost of d-schemes
Verfasser: Tindell, Ralph
Sprache: Englisch
Erscheinungsjahr: 1976
Quelle: Saarbrücken, 1976
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: 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 zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-40382
hdl:20.500.11880/26138
http://dx.doi.org/10.22028/D291-26082
Schriftenreihe: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Band: 1976/10
SciDok-Publikation: 27-Jul-2011
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1976_10.pdf3,15 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.