Výsledky vyhledávání - "light linear logic"

Light types for polynomial time computation in lambda calculus

Publikováno v: Information and Computation. 207(1):41-62

We present a polymorphic type system for lambda calculus ensuring that well-typed programs can be executed in polynomial time: dual light affine logic (DLAL). DLAL has a simple type language with a linear and an intuitionistic type arrow, and one mod

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::41fae7672d7518ce9cb115d603ffacaa

Zobrazit plný text záznamu

Controlling Program Extraction in Light Logics

Autor: Marc Lasson

Publikováno v: Typed Lambda Calculi and Applications 10th International Conference, TLCA 2011, Novi Sad, Serbia, June 1-3, 2011. Proceedings
Typed Lambda Calculi and Applications 10th International Conference, TLCA 2011, Novi Sad, Serbia, June 1-3, 2011.
Typed Lambda Calculi and Applications 10th International Conference, TLCA 2011, Novi Sad, Serbia, June 1-3, 2011., Jun 2011, Novi Sad, Serbia. pp.123-137, ⟨10.1007/978-3-642-21691-6⟩
Lecture Notes in Computer Science ISBN: 9783642216909
TLCA

15 pages; International audience; We present two refinements, based on program extraction in elementary affine logic and light affine logic, of Krivine & Leivant's system FA2. This system allows higher-order equations to specify the computational con

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2d62ee3c97a9615d6b72d233186afcb9
https://hal.archives-ouvertes.fr/hal-00605654

Zobrazit plný text záznamu

A PolyTime Functional Language from Light Linear Logic

Autor: Patrick Baillot, Virgile Mogbil, Marco Gaboardi

Publikováno v: Programming Languages and Systems ISBN: 9783642119569
ESOP
Programming Languages and Systems 19th European Symposium on Programming, ESOP 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Paphos, Cyprus, March 20-28, 2010. Proceedings
19th European Symposium on Programming (ESOP 2010)
19th European Symposium on Programming (ESOP 2010), Mar 2010, Paphos, Cyprus. pp. 104-124, ⟨10.1007/978-3-642-11957-6⟩

30 pages; International audience; We introduce a typed functional programming language LPL (acronym for Light linear Programming Language) in which all valid programs run in polynomial time, and which is complete for polynomial time functions. LPL is

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f9d27bad09918e655b4493bb7518df83
https://doi.org/10.1007/978-3-642-11957-6_7

Zobrazit plný text záznamu

Light Logics and Optimal Reduction: Completeness and Complexity

Autor: Patrick Baillot, Ugo Dal Lago, Paolo Coppola

Publikováno v: Information and Computation
Information and Computation, Elsevier, 2011, 209 (2), pp.118-142. ⟨10.1016/j.ic.2010.10.002⟩
Proceedings of Symposium on Logic in Computer Science (LICS '07)
Symposium on Logic in Computer Science (LICS '07)
Symposium on Logic in Computer Science (LICS '07), 2007, Wroclaw, Poland. à paraître
LICS
Information and Computation, 2011, 209 (2), pp.118-142. ⟨10.1016/j.ic.2010.10.002⟩

Typing of lambda-terms in Elementary and Light Affine Logic (EAL, LAL, resp.) has been studied for two different reasons: on the one hand the evaluation of typed terms using LAL (EAL, resp.) proof-nets admits a guaranteed polynomial (elementary, resp

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fd5894ecf49af54924d68f585c166de4
http://hdl.handle.net/11585/60340

Zobrazit plný text záznamu

An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus

Autor: Baillot, Patrick, Pedicini, Marco

Publikováno v: 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

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 structu

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e2e0e25a488e75513bb4b51ef864a998
https://hal.archives-ouvertes.fr/hal-00085547

Zobrazit plný text záznamu

Akademický článek

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Type inference for light affine logic via constraints on words

Autor: Patrick Baillot

Publikováno v: Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2004, 328(3), pp.289-323

Light Affine Logic (LAL) is a system due to Girard and Asperti capturing the complexity class P in a proof-theoretical approach based on Linear Logic. LAL provides a typing for lambda-calculus which guarantees that a well-typed program is executable

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cc4ee49a9aa7b4000f1d7869eff9f498
https://hal.archives-ouvertes.fr/hal-00084611

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání