Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-26T12:54:39.589Z Has data issue: false hasContentIssue false
  • English
  • Français

Transport of finiteness structures and applications

Published online by Cambridge University Press:  05 December 2016

CHRISTINE TASSON  and
LIONEL VAUX
CHRISTINE TASSON
Affiliation:
Univ Paris Diderot, Sorbonne Paris Cité, IRIF, UMR 8243, CNRS, F-75205 Paris, France Email: [email protected]
LIONEL VAUX
Affiliation:
Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We describe a general construction of finiteness spaces which subsumes the interpretations of all positive connectors of linear logic. We then show how to apply this construction to prove the existence of least fixpoints for particular functors in the category of finiteness spaces: These include the functors involved in a relational interpretation of lazy recursive algebraic datatypes along the lines of the coherence semantics of system T.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 28 , Special Issue 7: Differential Linear Logic, Nets and Other Quantitative and Parallel Approaches to Proof-Theory , August 2018 , pp. 1061 - 1096
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Amadio, R. and Curien, P.-L. (1998). Domains and Lambda-Calculi, volume 46 of Cambridge Tracts in Theoretical Computer Science, Vol. 2, Cambridge University Press, New York, NY, USA.CrossRefGoogle Scholar
Backhouse, R.C., de Bruin, P.J., Hoogendijk, P.F., Malcolm, G., Voermans, E. and van der Woude, J. (1991). Polynomial relators. In: Nivat, M., Rattray, C., Rus, T. and Scollo, G. (eds.) AMAST, Workshops in Computing, Springer, 303–326.Google Scholar
Backhouse, R.C. and Hoogendijk, P.F. (2003). Generic properties of datatypes. In: Backhouse, R.C. and Gibbons, J. (eds.) Generic Programming, Lecture Notes in Computer Science, vol. 2793, Springer, 97–132.Google Scholar
Baelde, D. and Miller, D. (2007). Least and greatest fixed points in linear logic. In: Dershowitz, N. and Voronkov, A. (eds.) LPAR, Lecture Notes in Computer Science, vol. 4790, Springer, 92–106.Google Scholar
Bierman, G.M. (1995). What is a categorical model of intuitionistic linear logic? In: Dezani, M. (ed.) Proceedings of Conference on Typed lambda calculus and Applications, Lecture Notes in Computer Science, vol. 902, Springer-Verlag.Google Scholar
Bird, R. and de Moor, O. (1997). Algebra of Programming, Prentice-Hall, Inc., Upper Saddle River, NJ, USA.Google Scholar
Bucciarelli, A., Ehrhard, T. and Manzonetto, G. (2007). Not enough points is enough, Computer Science Logic, Lecture Notes in Computer Science, vol. 4646, Springer, Berlin, 298–312.Google Scholar
Carboni, A., Kasangian, S. and Street, R. (1984). Bicategories of spans and relations. Journal of Pure and Applied Algebra 33 (3) 259–267.CrossRefGoogle Scholar
Carboni, A., Kelly, G.M. and Wood, R.J. (1991). A 2-categorical approach to change of base and geometric morphisms. I. Cahiers Topologie Géom. Différentielle Catég. 32 (1) 47–95.Google Scholar
Clairambault, P. (2010). Logique et Interaction: une Étude Sémantique de la Totalité, Thèse d'université, Université Paris 7.Google Scholar
Curien, P.-L. (ed.) (2009). Typed Lambda Calculi and Applications, In: Proceedings of 9th International Conference, TLCA 2009, Brasilia, Brazil, July 1–3, 2009., Lecture Notes in Computer Science, vol. 5608, Springer.Google Scholar
de Carvalho, D. (2008). Execution time of lambda-terms via denotational semantics and intersection types. Technical Report, Rapport de recherche INRIA n° 6638.Google Scholar
Ehrhard, T. (1993). Hypercoherences: A strongly stable model of linear logic. Mathematical Structures in Computer Science 3 (4) 365–385.Google Scholar
Ehrhard, T. (2005). Finiteness spaces. Mathematical Structures in Computer Science 15 (4) 615–646.Google Scholar
Ehrhard, T. and Laurent, O. (2007). Interpreting a finitary pi-calculus in differential interaction nets. In: Caires, L. and Vasconcelos, V.T. (eds.) Concurrency Theory (CONCUR '07), Lecture Notes in Computer Science, vol. 4703, Springer, 333–348.Google Scholar
Ehrhard, T. and Regnier, L. (2003). The differential lambda-calculus. Theoretical Computer Science 309 1–41.Google Scholar
Ehrhard, T. and Regnier, L. (2005). Differential interaction nets. Electronic Notes in Theoretical Computer Science 123 35–74.Google Scholar
Ehrhard, T. and Regnier, L. (2006). Böhm trees, Krivine's machine and the Taylor expansion of λ-terms. In: Beckmann, A., Berger, U., Löwe, B. and Tucker, J.V. (eds.) CiE, Lecture Notes in Computer Science, vol. 3988, Springer, 186–197.Google Scholar
Fernández, M., Mackie, I., Sato, S. and Walker, M. (2009). Recursive functions with pattern matching in interaction nets. Electronic Notes in Theoretical Computer Science 253 (4) 55–71.Google Scholar
Gimenez, S. (2009). Programmer, Calculer et Raisonner avec les Réseaux de la Logique Linéaire, Thèse d'université, Université Paris 7.Google Scholar
Girard, J.-Y. (1988). Normal functors, power series and lambda-calculus. Annals of Pure and Applied Logic 37 (2) 129–177.CrossRefGoogle Scholar
Girard, J.-Y., Taylor, P. and Lafont, Y. (1989). Proofs and Types, Cambridge University Press, New York, NY, USA.Google Scholar
Hoogendijk, P. and De Moor, O. (2000). Container types categorically. Journal of Functional Programming 10 191–225.Google Scholar
Hyland, M. and Schalk, A. (2003). Glueing and orthogonality for models of linear logic. Theoretical Computer Science 294 (1/2) 183–231.Google Scholar
Lambek, J. and Scott, P. (1986). Introduction to Higher Order Categorical Logic, Cambridge Studies in Advanced Mathematics, vol. 7, Cambridge University Press.Google Scholar
Lambek, J. and Scott, P.J. (1988). Introduction to Higher Order Categorical Logic, Cambridge University Press, New York, NY, USA.Google Scholar
Loader, R. (1994). Linear logic, totality and full completeness. In: Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), IEEE Computer Society, 292–298.Google Scholar
Mac Lane, S. (1998). Categories for the Working Mathematician, Springer.Google Scholar
Pagani, M. and Tasson, C. (2009). The inverse Taylor expansion problem in Linear Logic. In: Pitts, A.M. (ed.) Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, IEEE Computer Society, 222–231.Google Scholar
Smyth, M.B. and Plotkin, G.D. (1982). The category-theoretic solution of recursive domain equations. SIAM Journal on Computing 11 (4) 761–783.Google Scholar
Tasson, C. (2009). Algebraic totality, towards completeness. In: Curien (2009), 325–340.Google Scholar
Thibault, M.-F. (1982). Pre-recursive categories. Journal of Pure and Applied Algebra 24 79–93.Google Scholar
Tranquilli, P. (2008). Intuitionistic differential nets and lambda-calculus. Theoretical Computer Science 412 (20) 1979–1997.Google Scholar
Vaux, L. (2009a). The algebraic lambda calculus. Mathematical Structures in Computer Science 19 (5) 1029–1059.CrossRefGoogle Scholar
Vaux, L. (2009b). Differential linear logic and polarization. In: Curien (2009), 371–385.Google Scholar
Vaux, L. (2009c). A non-uniform finitary relational semantics of system T. In: Matthes, R. and Uustalu, T. (eds.) Proceedings of the 6th Workshop on Fixed Points in Computer Science, Institute of Cybernetics at Tallinn University of Technology.Google Scholar