Non-primitive Recursive Function Definitions
AbstractThis paper presents an approach to the problem of introducing
non-primitive recursive function definitions in higher order logic. A
recursive specification is translated into a domain theory version, where
the recursive calls are treated as potentially non-terminating. Once we
have proved termination, the original specification can be derived easily.
A collection of algorithms are presented which hide the domain theory
from a user. Hence, the derivation of a domain theory specification
has been automated completely, and for well-founded recursive function
specifications the process of deriving the original specification from the
domain theory one has been automated as well, though a user must
supply a well-founded relation and prove certain termination properties
of the specification. There are constructions for building well-founded
How to Cite
Agerholm, S. (1995). Non-primitive Recursive Function Definitions. BRICS Report Series, 2(36). https://doi.org/10.7146/brics.v2i36.19939
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.