Parameterized Recursion Theory- A Tool for the Systematic Classification of Specification Methods

Abstract We examine four specification methods with increasing expressiveness. Parameterized recursion theory allows to characterize the power of parameterization in the methods, using a computational model based on Moschovakis ' search computability. The four specification methods can be characterized by four different notions of semicomputable parameterized abstract data type, which differ in the availability of the parameter algebra and of nondeterminism. These characterizations further lead to different algebraic properties of specifiable PADTs. Together with example PADTs, they enable us to prove a hierarchy theorem