The interesting questions one can ask about program schemas include questions about the power of classes of shemas and their decision problems viz. halting, divergence, equivalence, etc. Considered first are the powers of schemas with various features: recursion, equality tests, and several data structures such as pushdown stacks, lists, queues and arrays. Then the decision problems for schemas with equality and with commutative and invertible functions are considered. Finally a generalized class of schemas is described in an attempt to unify the various classes of uninterpreted and semi-interpreted schemas and schemas with special data structures. (Author).

The authors consider the power of several programming features such as counters, pushdown stacks, queues, arrays, recursion and equality. In the study program schemas are used as the model for computation. The relations between the powers of these features is completely described by a comparison diagram. (Author).

The author considers the class of linear recursive programs. A linear recursive program is a set of procedures where each procedure can make at most one recursive call. The conventional stack implementation of recursion requires time and space both proportional to n, the depth of recursion. It is shown that in order to implement linear recursion so as to execute in time n one doesn't need space proportional to n : (n sup epsilon) for arbitrarily small epsilon will do. It is also known that with constant space one can implement linear recursion in time (n sup 2). The author shows that one can do much better: (n sup(1 + epsilon) for arbitratily small epsilon. The author also describes an algorithm that lies between these two: it takes time n.log(n) and space log(n). It is shown that several problems are closely related to the linear recursion problem, for example, the problem of reversing an input tape given a finite automaton with several one-way heads. By casting all these problems into a canonical form, efficient solutions are obtained simultaneously for all. (Author).

The authors discuss the class of program schemas augmented with equality tests, that is, tests of equality between terms. In the first part of the paper the authors discuss and illustrate the power of equality tests. It turns out that the class of program schemas with equality is more powerful than the maximal classes of schemas suggested by other investigators. In the second part of the paper the authors discuss the decision problems of program schemas with equality. It is shown for example that while the decision problems normally considered for schemas (such as halting, divergence, equivalence, isomorphism and freedom) are solvable for Ianov schemas, they all become unsolvable if general equality tests are added. The authors suggest, however, limited equality tests which can be added to certain subclasses of program schemas while preserving their solvable properties. (Author).