Open AccessNon-primitive Recursive Function Definitions
Author(s) -
Sten Agerholm
Publication year - 1995
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v2i36.19939
Subject(s) - domain theory , μ operator , primitive recursive function , function (biology) , domain (mathematical analysis) , computer science , programming language , algorithm , order (exchange) , theoretical computer science , discrete mathematics , mathematics , recursive functions , algebra over a field , pure mathematics , evolutionary biology , biology , mathematical analysis , finance , economics
This 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 relations easily.