Non-primitive Recursive Function Definitions

This paper presents an approach to the problem of introducingnon-primitive recursive function definitions in higher order logic. Arecursive specification is translated into a domain theory version, wherethe recursive calls are treated as potentially non-terminating. Once wehave proved termination, the original specification can be derived easily.A collection of algorithms are presented which hide the domain theoryfrom a user. Hence, the derivation of a domain theory specificationhas been automated completely, and for well-founded recursive functionspecifications the process of deriving the original specification from thedomain theory one has been automated as well, though a user mustsupply a well-founded relation and prove certain termination propertiesof the specification. There are constructions for building well-foundedrelations easily