An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus. - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus.

Résumé

This paper brings together two lines of research: implicit characterization of complexity classes by Linear Logic (LL) on the one hand, and computation over an arbitrary ring in the Blum-Shub-Smale (BSS) model on the other. Given a fixed ring structure K we define an extension of Terui's light affine lambda-calculus typed in LAL (Light Affine Logic) with a basic type for K. We show that this calculus captures the polynomial time function class FP(K): every typed term can be evaluated in polynomial time and conversely every polynomial time BSS machine over K can be simulated in this calculus.
Fichier principal
Vignette du fichier
BssLal160706.pdf (208 Ko) Télécharger le fichier

Dates et versions

hal-00085547 , version 1 (12-07-2006)
hal-00085547 , version 2 (20-07-2006)
hal-00085547 , version 3 (08-08-2006)

Identifiants

  • HAL Id : hal-00085547 , version 2

Citer

Patrick Baillot, Marco Pedicini. An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus.. 8th International Workshop on Logic and Computational Complexity Seattle, August 10 - 11, 2006 (Satellite Workshop of FLOC-LICS 2006), 2006, Seattle, United States. ⟨hal-00085547v2⟩
66 Consultations
152 Téléchargements

Partager

Gmail Facebook X LinkedIn More