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.
@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} }
Feedback for Dagstuhl Publishing