Computer Science – Logic in Computer Science
Scientific paper
2006-08-08
8th International Workshop on Logic and Computational Complexity Seattle, August 10 - 11, 2006 (Satellite Workshop of FLOC-LIC
Computer Science
Logic in Computer Science
11 pages. A preliminary version appeared as Research Report IAC CNR Roma, N.57 (11/2004), november 2004
Scientific paper
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.
Baillot Patrick
Pedicini Marco
No associations
LandOfFree
An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-247496