DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2013.101

A characterization of the Taylor expansion of lambda-terms

Authors: Pierre Boudes, Fanny He, and Michele Pagani

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)

Abstract

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.

Cite as

Pierre Boudes, Fanny He, and Michele Pagani. A characterization of the Taylor expansion of lambda-terms. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 101-115, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{boudes_et_al:LIPIcs.CSL.2013.101,
  author =	{Boudes, Pierre and He, Fanny and Pagani, Michele},
  title =	{{A characterization of the Taylor expansion of lambda-terms}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{101--115},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.101},
  URN =		{urn:nbn:de:0030-drops-41925},
  doi =		{10.4230/LIPIcs.CSL.2013.101},
  annote =	{Keywords: Lambda-Calculus, B\"{o}hm trees, Differential Lambda-Calculus, Linear Logic}
}

Search Results

Documents authored by He, Fanny

A characterization of the Taylor expansion of lambda-terms

Abstract

Cite as

Thanks for your feedback!

Could not send message