Avec Fanny He et Michele Pagani
A characterization of the Taylor expansion of lambda-terms
Expansion Land par Andrew V Kearns (cc-by).
, par
The Taylor expansion of $\lambda$-terms, as introduced by Ehrhard and Regnier, expresses a $\lambda$-term as a series of multi-linear terms, called simple terms, which capture bounded computations. Normal forms of Taylor expansions give a notion of infinitary normal forms, refining the notion of Böhm trees in a quantitative setting.
We give the algebraic conditions over a set of normal simple terms which characterize the property of being the normal form of the Taylor expansion of a $\lambda$-term. From this full completeness result, we give further conditions which semantically describe normalizable and total $\lambda$-terms.
RSS 2.0
