SciDok

Eingang zum Volltext in SciDok

Lizenz

Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-40382
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/4038/


The exponential storage cost of d-schemes

Tindell, Ralph

Quelle: (1976) Saarbr├╝cken, 1976
pdf-Format:
Dokument 1.pdf (3.152 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Institut: Fachrichtung 6.2 - Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Report (Bericht)
Schriftenreihe: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universit├Ąt des Saarlandes
Bandnummer: 1976/10
Sprache: Englisch
Erstellungsjahr: 1976
Publikationsdatum: 27.07.2011
Kurzfassung auf Englisch: 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.
Lizenz: Standard-Veröffentlichungsvertrag

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English