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
BssLal070806.pdf (190.73 Ko) Télécharger le fichier
Loading...

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

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-00085547v3⟩
65 Consultations
150 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More