Show simple item record

dc.contributor.authorBrown, John Stevenen_US
dc.description.abstractThe concept of a program schema, which represents the skeleton of a computer program, is important for its potential and actual applicability to code optimization, to understanding the behavior of programs using various control and data structure features, and to developing a theory of information flow as related to program form and power. In this study tow storage devices, the tape and the queue, are considered, and their effect on the schema power hierarchy explored. The behavior and relative capability of each one of the various types of tapes and queues is discussed in the light of the ways in which information is allowed to move, according to the inherent characteristics of the devices. Main results include the facts that addition of a single tape unit to the simplest schema class P gives no additional power, and that the basic cyclic nature of queues and the persistence of data on tapes are important power determinants. An attempt is made to bridge the gap between schema theory and actual programs not only by studying models of actual storage units but also by allowing an arbitrarily long (but finite) input stream. Such an extension generally upsets the onion-like power inclusions of the finite input hierarchy because of the calculations possible on the implicitly-input arbitrary integer, which is the number of inout values. The information flow characteristics of the data structures associated with a particular schema class may allow such an arbitrary input to be viewed exactly once, exactly twice, or in general m times, and such distinctions give rise to differences in computational power. Requirements insuring that the interconnection of schemata form a schema with the union of the capabilities of the subschemata are considered. The hierarchy of schemata without the identity assignment is also studied, and it is demonstrated that in the simplest class $P$ and the universal class $P_{Ae}$ no loss of power results from prohibiting identity assignments. Discussion of the as-yet-unsolved problem of the power of the class $P_{(2b,0)}$ and its associated derivatives is presented. A summary of prospects for developing program schema research in several different potentially practical directions concludes the work.en_US
dc.format.extent11106146 bytes
dc.format.extent2277888 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleProgram Schemata and Information Flow: A Study of Some Aspects of the Schema Power of Data Structuresen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record