pith. sign in

arxiv: cs/0507007 · v4 · pith:P6PUVYK3new · submitted 2005-07-04 · 💻 cs.GT

Strong normalisation for applied lambda calculi

classification 💻 cs.GT
keywords normalisationappliedconstantslambdanormalisingstrongstronglysystem
0
0 comments X
read the original abstract

We consider the untyped lambda calculus with constructors and recursively defined constants. We construct a domain-theoretic model such that any term not denoting bottom is strongly normalising provided all its `stratified approximations' are. From this we derive a general normalisation theorem for applied typed lambda-calculi: If all constants have a total value, then all typeable terms are strongly normalising. We apply this result to extensions of G\"odel's system T and system F extended by various forms of bar recursion for which strong normalisation was hitherto unknown.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.