Optimality & the linear substitution calculus | ||
| dc.conicet.organizacion | Universidad de Buenos Aires | |
| dc.conicet.organizacion | Université Paris Diderot - Paris 7 | |
| dc.conicet.organizacion | Stevens Institute of Technology | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Stevens Institute of Technology | |
| dc.conicet.organizacion | Universidad Nacional de Quilmes | |
| dc.contributor.author | Barenbaum, Pablo | |
| dc.contributor.author | Bonelli, Eduardo Augusto | |
| dc.date.issued | 2017-09 | |
| dc.description.abstract | We lift the theory of optimal reduction to a decomposition of the lambda calculus known as the Linear Substitution Calculus (LSC). LSC decomposes β-reduction into finer steps that manipulate substitutions in two distinctive ways: it uses context rules that allow substitutions to act "at a distance" and rewrites modulo a set of equations that allow substitutions to "float" in a term. We propose a notion of redex family obtained by adapting Lévy labels to support these two distinctive features. This is followed by a proof of the finite family developments theorem (FFD). We then apply FFD to prove an optimal reduction theorem for LSC. We also apply FFD to deduce additional novel properties of LSC, namely an algorithm for standardisation by selection and normalisation of a linear call-by-need reduction strategy. All results are proved in the axiomatic setting of Glauert and Khashidashvili´s Deterministic Residual Structures. | es |
| dc.description.fil | Fil: Barenbaum, Pablo. Universidad de Buenos Aires; Argentina. Université Paris Diderot - Paris 7; Francia. Stevens Institute of Technology; Estados Unidos. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Bonelli, Eduardo Augusto. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Stevens Institute of Technology; Estados Unidos. Universidad Nacional de Quilmes; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Barenbaum, Pablo; Bonelli, Eduardo Augusto; Optimality & the linear substitution calculus; Schloss Dagstuhl. Leibniz-Zentrum für Informatik; Leibniz International Proceedings in Informatics, LIPIcs; 84; 9-2017; 1-16 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 1868-8969 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/41112 | |
| dc.journal.ciudad | Leibniz | es |
| dc.journal.pagination | 1-16 | es |
| dc.journal.pais | Alemania | es |
| dc.journal.title | Leibniz International Proceedings in Informatics, LIPIcs | es |
| dc.journal.volume | 84 | es |
| dc.language.iso | eng | es |
| dc.publisher | Schloss Dagstuhl. Leibniz-Zentrum für Informatik | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.4230/LIPIcs.FSCD.2017.9 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://drops.dagstuhl.de/opus/volltexte/2017/7730/ | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by/2.5/ar/ | * |
| dc.subject | Explicit Substitutions | es |
| dc.subject | Lambda Calculus | es |
| dc.subject | Optimal Reduction | es |
| dc.subject | Rewriting | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Optimality & the linear substitution calculus | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.2cf65672-4c60-4b3b-8d80-3876d3fb4d92_A.pdf
- Tamaño:
- 656.79 KB
- Formato:
- Adobe Portable Document Format