Proving termination of normalization functions for conditional expressions
\textit{R. Boyer} and \textit{J. Moore} have discussed a function that puts conditional expressions into normal form [A computational logic (1979; Zbl 0448.68020)]. It is difficult to prove that this function terminates on all inputs. Three termination proofs are compared: (1) using a measure function, (2) in domain theory using LCF, (3) showing that its recursion relation, defined by the pattern of recursive calls, is well founded. The last two proofs are essentially the same though conducted in markedly different logical frameworks. An obviously total variant of the normalize function is presented as the ``computational meaning of those two proofs. A related function makes nested recursive calls. The three termination proofs become more complex: termination and correctness must be proved simultaneously. The recursion relation approach seems flexible enough to handle subtle termination proofs where previously domain theory seemed essential.
- Constructing recursion operators in intuitionistic type theory
- Synthesis of ML programs in the system Coq
- On proving the termination of algorithms by machine
- Representing inductively defined sets by wellorderings in Martin-Löf's type theory
- scientific article; zbMATH DE number 1670762 (Why is no real title available?)
- scientific article; zbMATH DE number 3557747 (Why is no real title available?)
- Size-based termination of higher-order rewriting
- Function definition in higher-order logic
- Normalising the associative law: An experiment with Martin-Löf's type theory
This page was built for publication: Proving termination of normalization functions for conditional expressions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101251)
