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 hdl:20.500.11880/26138 http://dx.doi.org/10.22028/D291-26082 |
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 | Size | Format | |
---|---|---|---|---|
fb14_1976_10.pdf | 3,15 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.