DROPS

Document

DOI: 10.4230/LIPIcs.TLCA.2015.288

Polynomial Time in the Parametric Lambda Calculus

Authors: Brian F. Redmond

Published in: LIPIcs, Volume 38, 13th International Conference on Typed Lambda Calculi and Applications (TLCA 2015)

Abstract

In this paper we investigate Implicit Computational Complexity via the parametric lambda calculus of Ronchi Della Rocca and Paolini. We show that a particular instantiation of the set of input values leads to a characterization of polynomial time computations in a similar way to Lafont’s Soft Linear Logic. This characterization is manifestly type-free and does not require any ad hoc extensions to the pure lambda calculus. Moreover, there is a natural extension to nondeterminism with the addition of explicit products.

Cite as

Brian F. Redmond. Polynomial Time in the Parametric Lambda Calculus. In 13th International Conference on Typed Lambda Calculi and Applications (TLCA 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 38, pp. 288-301, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{redmond:LIPIcs.TLCA.2015.288,
  author =	{Redmond, Brian F.},
  title =	{{Polynomial Time in the Parametric Lambda Calculus}},
  booktitle =	{13th International Conference on Typed Lambda Calculi and Applications (TLCA 2015)},
  pages =	{288--301},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-87-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{38},
  editor =	{Altenkirch, Thorsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TLCA.2015.288},
  URN =		{urn:nbn:de:0030-drops-51705},
  doi =		{10.4230/LIPIcs.TLCA.2015.288},
  annote =	{Keywords: Parametric Lambda Calculus, Polynomial Time Complexity, Combinators, Nondeterminism and Explicit Products, Implicit Computational Complexity}
}

Search Results

Documents authored by Redmond, Brian F.

Polynomial Time in the Parametric Lambda Calculus

Abstract

Cite as

Thanks for your feedback!

Could not send message