Non-primitive Recursive Function Definitions
Non-primitive Recursive Function Definitions
复制标题
非原始递归函数定义
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Sten Agerholm
中科院分区：
文献类型：
--
作者：
Sten Agerholm
本文提出了一种以高阶逻辑引入非递归函数定义的问题的方法。递归规范被翻译成域理论版本，其中递归调用被视为潜在的非终止。一旦我们证明了终止，就可以轻松得出原始规范。提出了一系列算法，该算法向用户隐藏了域理论。因此，域理论规范的推导已完全自动化，对于有充分的递归函数规范，从域理论中得出原始规范的过程也已自动化，尽管用户必须提供建立良好的关系并证明规范的某些终止属性。有一些容易建立有充分基础的关系的构造。
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.