Subrecursive program schemata I & II(I. Undecidable equivalence problems, II. Decidable equivalence problems)
Robert L. Constable, Steven S. Muchnick · 1972
The study of program schemata and the study of subrecursive programming languages are both concerned with limiting program structure in order to permit a more complete analysis of algorithms while retaining sufficiently rich computing power to allow interesting algorithms. In this paper we combine these approaches by defining classes of subrecursive program schemata and investigating their equivalence problems. Since the languages are all subrecursive, any scheme written in any one of them must halt (as long as we assume the basic functions and predicates are all total). Hence equivalence of schemes is the first question of interest we can ask about these languages.