An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus
| Autor: | Baillot, Patrick, Pedicini, Marco |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique de Paris-Nord (LIPN), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Istituto per le Applicazioni del Calcolo 'Mauro Picone' (IAC), Consiglio Nazionale delle Ricerche [Roma] (CNR), Cooperation project 'Interaction et complexité' CNR/CNRS, projects GEOCAL (ACI) , NO-COST (ANR) ., Baillot, P, Pedicini, Marco |
| Jazyk: | angličtina |
| Rok vydání: | 2006 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science Computer Science::Logic in Computer Science polynomial time complexity linear logic [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] light linear logic lambda-calculus Blum-Shub-Smale model Logic in Computer Science (cs.LO) |
| Zdroj: | 8th International Workshop on Logic and Computational Complexity Seattle, August 10-11, 2006 (Satellite Workshop of FLOC-LICS 2006) 8th International Workshop on Logic and Computational Complexity Seattle, August 10-11, 2006 (Satellite Workshop of FLOC-LICS 2006), 2006, Seattle, United States |
| Popis: | 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. Comment: 11 pages. A preliminary version appeared as Research Report IAC CNR Roma, N.57 (11/2004), november 2004 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|