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 them finitary in the sense of Ehrhard's finiteness spaces.
@article{ITA_2013__47_1_111_0,
author = {Vaux, Lionel},
title = {A non-uniform finitary relational semantics of system $T$},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {47},
year = {2013},
pages = {111-132},
doi = {10.1051/ita/2012031},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2013__47_1_111_0}
}
Vaux, Lionel. A non-uniform finitary relational semantics of system $T$. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) pp. 111-132. doi : 10.1051/ita/2012031. http://gdmltest.u-ga.fr/item/ITA_2013__47_1_111_0/
[1] and , 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. | MR 2503407 | Zbl 1146.68027
[2] , , , , and , 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.
[3] and , 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. | Zbl 1274.68210
[4] , Graph models of lambda-calculus at work, and variations. Math. Struct. Comput. Sci. 16 (2006) 185-221. | MR 2228853 | Zbl 1097.03011
[5] , 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. | MR 520840 | Zbl 0382.68041
[6] , and , 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. | MR 2540209 | Zbl 1179.03021
[7] , and , 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. | MR 2544240 | Zbl 1211.03026
[8] and , On probabilistic coherence spaces, unpublished draft (2008). Available on http://hal.archives-ouvertes.fr/hal-00280462.
[9] , Sémantiques de la logique linéaire et temps de calcul, Ph.D. thesis, Université Aix-Marseille 2 (2007).
[10] , Execution time of lambda-terms via denotational semantics and intersection types. Technical report 6638. INRIA (2008).
[11] , Finiteness spaces. Math. Struct. Comput. Sci. 15 (2005) 615-646. | MR 2158033 | Zbl 1084.03048
[12] and , Interpreting a finitary pi-calculus in differential interaction nets. Inform. Comput. 208 (2010) 606-633. | MR 2663520 | Zbl 1205.68242
[13] and , The differential lambda-calculus. Theor. Comput. Sci. 309 (2003) 1-41. | MR 2016523 | Zbl 1070.68020
[14] and , Differential interaction nets. Electron. Notes Theoret. Comput. Sci. 123 (2005) 35-74. | MR 2207408 | Zbl 1113.03054
[15] and , 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. | Zbl 1130.68054
[16] , The system F of variable types, fifteen years later. Theoret. Comput. Sci. 45 (1986) 159-192. | MR 867281 | Zbl 0623.03013
[17] , Linear logic. Theoret. Comput. Sci. 50 (1987) 1-102. | MR 899269 | Zbl 0625.03037
[18] , Normal functors, power series and lambda-calculus. Ann. Pure Appl. Log. 37 (1988) 129-177. | MR 926748 | Zbl 0646.03056
[19] , and , Proofs and Types, Cambridge University Press, Cambridge Tracts. Theoret. Comput. Sci. 7 (1989). | MR 1003608 | Zbl 0671.68002
[20] and , Container types categorically. J. Funct. Program. 10 (2000) 191-225. | MR 1767938 | Zbl 0959.68023
[21] and , Glueing and orthogonality for models of linear logic. Theoret. Comput. Sci. 294 (2003) 183-231. | MR 1964781 | Zbl 1029.03051
[22] and , Introduction to Higher Order Categorical Logic, Cambridge University Press. Cambridge Stud. Adv. Math. 7 (1988). | MR 939612 | Zbl 0642.03002
[23] , Categorical semantics of linear logic. Société Mathématique de France. Interact. Models Comput. Program Behaviour Panor. 27 (2009) 1-196. | MR 2675257 | Zbl 1206.03052
[24] and , 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. | MR 2932387
[25] , 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. | MR 1079086 | Zbl 0925.03149
[26] , Data types as lattices. SIAM J. Comput. 5 (1976) 522-587. | MR 437330 | Zbl 0337.02018
[27] , Completeness, invariance and lambda-definability. J. Symb. Log. 47 (1982) 17-26. | MR 644749 | Zbl 0487.03006
[28] , 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. | MR 2550057 | Zbl 1246.03081
[29] and , Transport of finiteness structures and applications. Math. Struct. Comput. Sci. (to appear).
[30] , Pre-recursive categories. J. Pure Appl. Algebra 24 (1982) 79-93. | MR 647582 | Zbl 0485.18005
[31] , Intuitionistic differential nets and lambda-calculus. Theoret. Comput. Sci. 412 (2011) 1979-1997. | MR 2814770 | Zbl 1223.03049
[32] , The algebraic lambda calculus. Math. Struct. Comput. Sci. 19 (2009) 1029-1059. | MR 2545510 | Zbl 1186.03025
[33] , 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. | MR 2550060 | Zbl 1246.03082