An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus
<|reference_start|>An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus: 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.<|reference_end|>
@article{baillot2006an,
    title={An Embedding of the BSS Model of Computation in Light Affine
  Lambda-Calculus},
    author={Patrick Baillot (LIPN), Marco Pedicini},
    journal={8th International Workshop on Logic and Computational Complexity
  Seattle, August 10 - 11, 2006 (Satellite Workshop of FLOC-LICS 2006),
  \'{E}tats-Unis d'Am\'{e}rique (2006)},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0608040},
    primaryClass={cs.LO}
}