Abstract
Paterson introduced the notions of freedom and liberality as semantic restrictions on the class of schemas. He felt that such restricted Might have solvable decision problems, realistic models of what classes of schemas and also be would generally be considered "good" programs. With the latter viewpoint in mind, two new classes of schemas are introduced in this thesis: the reachable schemas and the semi free schemas. Several decision problems for these classes, and translatability between these classes and other semantically restricted schema classes are studied. Relationships between various classes of schemas are also considered. An investigation is made of the preservation of semantic properties by is morph SM, functional Similarity, strong equivalency and weak equivalence. This allows a distinction to be made between properties, which are inherent in the class of functions represented by a schema, regardless of the algorithm used to compute it, and those properties which are dependent upon the algorithm or its encoding. Two types of interpretations for schemas are defined: point wise interpretations and function interpretations. The relationships between these types of interpretations are studied. It is seen that corresponding to the set of all finite consistent paths of a schema executed under point wise interpretations, there is a single effectively constructible function interpretation of that schema which has the same set of finite consistent-paths. The equivalence of certain semantic properties of schemas follows from this result. This result also facilitates the consideration of the inheritance of schema properties by programs, and the inheritance of program properties by schemas. Finally, several classes of programs, which are the analogues of the schema classes, are introduced. A study is made of translatability and decidability questions for these classes of programs, and it is demonstrated that results similar to those for schemas hold in most cases.