An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus
| dc.creator | Baillot, Patrick | |
| dc.creator | Pedicini, Marco | |
| dc.date | 2006-08-08 | |
| dc.date.accessioned | 2026-07-07T07:19:58Z | |
| dc.date.available | 2026-07-07T07:19:58Z | |
| dc.description | 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. | |
| dc.description | 11 pages. A preliminary version appeared as Research Report IAC CNR Roma, N.57 (11/2004), november 2004 | |
| dc.identifier | https://arxiv.org/abs/cs/0608040 | |
| dc.identifier | http://arxiv.org/abs/cs/0608040 | |
| dc.identifier | 8th International Workshop on Logic and Computational Complexity Seattle, August 10 - 11, 2006 (Satellite Workshop of FLOC-LICS 2006), États-Unis d'Amérique (2006) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/114828 | |
| dc.subject | Logic in Computer Science | |
| dc.title | An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus | |
| dc.type | text |