Article contents
A non-uniform finitary relational semantics of systemT∗
Published online by Cambridge University Press: 10 January 2013
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
We study iteration and recursion operators in the denotational semantics of typedλ-calculi derived from the multiset relational model of linear logic.Although these operators are defined as fixpoints of typed functionals, we prove themfinitary in the sense of Ehrhard’s finiteness spaces.
Information
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 47 , Issue 1: 6th Workshop on Fixed Points in Computer Science (FICS'09) , January 2013, pp. 111 - 132
- Copyright
- © EDP Sciences 2013
References
P. Arrighi and G. Dowek, Linear-algebraic lambda-calculus : higher-order, encodings, and confluence, in Proc. 19th Int. Conf. on Rewriting Techniques and Applications, RTA 2008, Hagenberg, July 2008, edited by A. Voronkov. Springer. Lect. Notes Comput. Sci. 5117 (2008) 17–31.
R.C. Backhouse, P.J. de Bruin, P.F. Hoogendijk, G. Malcolm, E. Voermans and J. van der Woude, Polynomial relators (extended abstract), in Proc. 2nd Int. Conf. on Algebraic Methodology and Software Technology, AMAST ’91 (Iowa City, IO, May 1991), edited by M. Nivat, C. Rattray, T. Rus and G. Scollo. Springer. Workshops in Computing (1992) 303–326.
R.C. Backhouse and P.F. Hoogendijk, Generic properties of datatypes, in Generic Programming : Advanced Lectures, edited by R.C. Backhouse and J. Gibbons. Springer. Lect. Notes Comput. Sci. 2793 (2003) 97–132.
Berline, C., Graph models of lambda-calculus at work, and variations. Math. Struct. Comput. Sci. 16 (2006) 185–221. Google Scholar
G. Berry, Stable models of typed lambda-calculi, in Proc. of 5th Int. Coll. on Automata, Languages and Programming, ICALP ’78, Udine, July 1978, edited by G. Ausiello and C. Böhm. Springer. Lect. Notes Comput. Sci. 62 (1978) 72–89.
A. Bucciarelli, T. Ehrhard and G. Manzonetto, Not enough points is enough, in Proc. 21st Workshop on Computer Science Logic, CSL 2007, Lausanne, Sept. 2007, edited by J. Duparc, T. A. Henzinger. Springer. Lect. Notes Comput. Sci. 4646 (2007) 298–312.
A. Bucciarelli, T. Ehrhard and G. Manzonetto, A relational model of a parallel and non-deterministic lambda-calculus, in Proc. Int. Symp. on Logical Foundations of Computer Science, LFCS 2009, Deerfield Beach, FL, Jan. 2009, edited by S.N. Artëmov and A. Nerode. Springer. Lect. Notes Comput. Sci. 5407 (2009) 107–121.
V. Danos and T. Ehrhard, On probabilistic coherence spaces, unpublished draft (2008). Available on http://hal.archives-ouvertes.fr/hal-00280462.
D. de Carvalho, Sémantiques de la logique linéaire et temps de calcul, Ph.D. thesis, Université Aix-Marseille 2 (2007).
D. de Carvalho, Execution time of lambda-terms via denotational semantics and intersection types. Technical report 6638. INRIA (2008).
Ehrhard, T. and Laurent, O., Interpreting a finitary pi-calculus in differential interaction nets. Inform. Comput. 208 (2010) 606–633. Google Scholar
Ehrhard, T. and Regnier, L., The differential lambda-calculus. Theor. Comput. Sci. 309 (2003) 1–41. Google Scholar
Ehrhard, T. and Regnier, L., Differential interaction nets. Electron. Notes Theoret. Comput. Sci. 123 (2005) 35–74. Google Scholar
T. Ehrhard and L. Regnier, Böhm trees, Krivine’s machine and the Taylor expansion of λ-terms, in Proc. 2nd Conf. on Computability in Europe, CiE 2006, Swansea, June/July 2006, edited by A. Beckmann, U. Berger, B. Löwe and J.V. Tucker. Springer. Lect. Notes Comput. Sci. 3988 (2006) 186–197.
Girard, J.-Y., The system F of variable types, fifteen years later. Theoret. Comput. Sci. 45 (1986) 159–192. Google Scholar
Girard, J.-Y., Normal functors, power series and lambda-calculus. Ann. Pure Appl. Log. 37 (1988) 129–177. Google Scholar
Girard, J.-Y., Taylor, P. and Lafont, Y., Proofs and Types, Cambridge University Press, Cambridge Tracts. Theoret. Comput. Sci. 7 (1989). Google Scholar
Hoogendijk, P. and De Moor, O., Container types categorically. J. Funct. Program. 10 (2000) 191–225. Google Scholar
Hyland, M. and Schalk, A., Glueing and orthogonality for models of linear logic. Theoret. Comput. Sci. 294 (2003) 183–231. Google Scholar
Lambek, J. and Scott, P.J., Introduction to Higher Order Categorical Logic, Cambridge University Press. Cambridge Stud. Adv. Math. 7 (1988). Google Scholar
Melliès, P.-A., Categorical semantics of linear logic. Société Mathématique de France. Interact. Models Comput. Program Behaviour Panor. 27 (2009) 1–196. Google Scholar
M. Pagani and C. Tasson, The inverse Taylor expansion problem in linear logic, in Proc. 24th Ann. IEEE Symp. on Logic in Computer Science, LICS ’09, Los Angeles, CA, Aug. 2009. IEEE CS Press (2009) 222–231.
M. Parigot, On the representation of data in lambda-calculus, in Proc. of 3rd Workshop on Computer Science Logic, CSL ’89, Kaiserslautern, Oct. 1989, edited by E. Börger, H. Kleine Büning and M.M. Richter. Springer. Lect. Notes Comput. Sci. 440 (1989) 309–321.
Statman, R., Completeness, invariance and lambda-definability. J. Symb. Log. 47 (1982) 17–26. Google Scholar
C. Tasson, Algebraic totality, towards completeness, in Proc. 9th Int. Conf. on Typed Lambda Calculi and Applications, TLCA 2009, Brasilia, July 2009, edited by P.-L. Curien. Springer. Lect. Notes Comput. Sci. 5608 (2009) 325–340.
C. Tasson and L. Vaux, Transport of finiteness structures and applications. Math. Struct. Comput. Sci. (to appear).
Tranquilli, P., Intuitionistic differential nets and lambda-calculus. Theoret. Comput. Sci. 412 (2011) 1979–1997. Google Scholar
Vaux, L., The algebraic lambda calculus. Math. Struct. Comput. Sci. 19 (2009) 1029–1059. Google Scholar
L. Vaux, Differential linear logic and polarization, in Proc. 9th Int. Conf. on Typed Lambda Calculi and Applications, TLCA 2009. Brasilia, July 2009, edited by P.-L. Curien. Springer. Lect. Notes Comput. Sci. 5608 (2009) 371–385.
You have Access
