Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-13T09:23:19.635Z Has data issue: false hasContentIssue false
  • English
  • Français

Jump from parallel to sequential proofs: exponentials

Published online by Cambridge University Press:  05 December 2016

PAOLO DI GIAMBERARDINO
PAOLO DI GIAMBERARDINO*
Affiliation:
Laboratoire d'Informatique de Paris Nord, 99, Avenue Jean Baptiste Clement 93430 Villetaneuse, Paris, France Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In previous works, by importing ideas from game semantics (notably Faggian–Maurel–Curien's ludics nets), we defined a new class of multiplicative/additive polarized proof nets, called J-proof nets. The distinctive feature of J-proof nets with respect to other proof net syntaxes, is the possibility of representing proof nets which are partially sequentialized, by using jumps (that is, untyped extra edges) as sequentiality constraints. Starting from this result, in the present work, we extend J-proof nets to the multiplicative/exponential fragment, in order to take into account structural rules: More precisely, we replace the familiar linear logic notion of exponential box with a less restricting one (called cone) defined by means of jumps. As a consequence, we get a syntax for polarized nets where, instead of a structure of boxes nested one into the other, we have one of cones which can be partially overlapping. Moreover, we define cut-elimination for exponential J-proof nets, proving, by a variant of Gandy's method, that even in case of ‘superposed’ cones, reduction enjoys confluence and strong normalization.

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. 1204 - 1252
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

Abramsky, S. (2003) Sequentiality vs. concurrency in games and logic. Mathematical Structures in Computer Science 13 (4) 531–565.Google Scholar
Accattoli, B. (January 2011) Jumping around the box: Graphical and operational studies on Lambda-Calculus and Linear Logic. Phd thesis, Università La Sapienza, Roma.Google Scholar
Accattoli, B. and Guerrini, S. (2009) Jumping boxes. In: CSL, 55–70.Google Scholar
Abramski, S. and Mellies, P.-A. (1999) Concurrent games and full completeness. In: LICS'99, IEEE, 431–442.CrossRefGoogle Scholar
Andreoli, J.-M. (1992) Logic programming with focusing proofs in linear logic. Journal of Logic and Computation 2 (3) 297–347.Google Scholar
Andreoli, J.M. (2002) Focussing proof-net construction as a middleware paradigm. In: Voronkov, A. (ed.) CADE'02, Lecture Notes in Computer Science, vol. 2392, Springer, 501–516.Google Scholar
Basaldella, M. and Faggian, C. (2009) Ludics with repetitions (exponentials, interactive types and completeness) In: LICS, 375–384.CrossRefGoogle Scholar
Bellin, G. and Van De Wiele, J. (1995) Subnets of proof-nets in MLL. In: Girard, J.-Y., Lafont, Y. and Regnier, L. (eds.) Advances in Linear Logic, London Mathematical Society Lecture Note Series, vol. 222, CUP, 249–270.Google Scholar
Boudes, P. (2009) Thick subtrees, games and experiments. In: TLCA, 65–79.Google Scholar
Curien, P.-L. and Faggian, C. (2005) L-nets, strategies and proof-nets. In: CSL'05, Lecture Notes in Computer Science, vol. 3634, Springer, 67–183.Google Scholar
Danos, V. (1990) Une Application de la Logique Linéaire à l'Ètude des Processus de Normalisation (principalement du λ-calcul) PhD Thesis, Univ. Paris 7, Paris.Google Scholar
Di Giamberardino, P. (2008) Jump from parallel to sequential proofs: on polarities and sequentiality in Linear Logic. Ph.D. thesis, Università di Roma Tre.Google Scholar
Di Giamberardino, P. (2011) Jump from parallel to sequential proofs: Additives. LIPN Technical report, avalaible at https://hal.archives-ouvertes.fr/hal-00616386v2.Google Scholar
Di Giamberardino, P. and Faggian, C. (2006) Jump from parallel to sequential proof: Multiplicatives. Lecture Notes in Computer Science, vol. 4207, Springer, Berlin/Heidelberg, 319–333.Google Scholar
Di Giamberardino, P. and Faggian, C. (2008) Proof nets sequentialisation in multiplicative linear logic. Annals of Pure and Applied Logic 155 (3) 173–182.Google Scholar
Ehrhard, T. and Laurent, O. (June 2010) Interpreting a finitary pi-calculus in differential interaction nets. Information and Computation 208 (6) 606–633.CrossRefGoogle Scholar
Faggian, C. and Hyland, M. (2002) Designs, disputes and strategies. In: CSL'02, Lecture Notes in Computer Science, vol. 2471, Springer Verlag.Google Scholar
Faggian, C. and Maurel, F. (2005) Ludics nets, a game model of concurrent interaction. In: LICS'05, IEEE.Google Scholar
Faggian, C. and Piccolo, M. (2007) Ludics is a model for the finitary linear pi-calculus. Lecture Notes in Computer Science, vol. 4583, Springer, Berlin/Heidelberg, 148–162.Google Scholar
Fouqueré, C. and Mogbil, V. (2008) Rewritings for polarized multiplicative and exponential proof structures. Electronic Notes in Theoretical Computer Science 203 (1) 109–121.Google Scholar
Gandy, R.O. (1980) Proofs of strong normalization. In: To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, Academic Press, London, 457–477.Google Scholar
Girard, J.-Y. (1972) Interpretation fonctionelle et élmination des coupures de l'arithmétique d'ordre supérieur. Thèse de doctorat, Université Paris VII.Google Scholar
Girard, J.-Y. (1987) Linear logic. TCS 50 1–102.Google Scholar
Girard, J.-Y. (1991a) Quantifiers in linear logic II. In: Corsi, G. and Sambin, G. (eds.) Nuovi problemi della Logica e della Filosofia della scienza CLUEB, Bologna, 79–90.Google Scholar
Girard, J.-Y. (1991b) A new constructive logic: classical logic. MSCS 1 (3) 255–296.Google Scholar
Girard, J.-Y. (1996) Proof-nets : The parallel syntax for proof-theory. In: Logic and Algebra, Lecture Notes in Pure and Appl. Math., vol. 180, 97–124.Google Scholar
Girard, J.-Y. (1998) Light linear logic. I&C 143 (2) 175–204.Google Scholar
Girard, J.-Y. (1999) On the meaning of logical rules. I: Syntax versus semantics. In: Computational logic (Marktoberdorf, 1997), NATO Adv. Sci. Inst. Ser. F Comput. Systems Sci., vol. 165, Springer, Berlin, 215–272.Google Scholar
Girard, J.-Y. (2000) On the meaning of logical rules II: Multiplicative/additive case. In: Foundation of Secure Computation, NATO Series F, vol. 175, IOS Press, 183–212.Google Scholar
Girard, J.-Y. (2001) Locus solum: From the rules of logic to the logic of rules. MSCS 11 301–506.Google Scholar
Girard, J.-Y. (2006) Le Point Aveugle, Tome I: vers la perfection. Hermann.Google Scholar
Girard, J.-Y. (2007) Le Point Aveugle, Tome II: vers l'imperfection. Hermann.Google Scholar
Honda, K. and Laurent, O. (May 2010) An exact correspondence between a typed pi-calculus and polarised proof-nets. Theoretical Computer Science 411 (22–24) 2223–2238.Google Scholar
Hyland, M. and Schalk, A. (2002) Games on graphs and sequentially realizable functionals. In: LICS'02, IEEE, 257–264.Google Scholar
Lafont, Y. (2004) Soft linear logic and polynomial time. Theoretical Computer Science (special issue on Implicit Computational Complexity) 318 (1–2) 163–180.Google Scholar
Laurent, O. (1999) Polarized proof-nets: Proof-nets for LC (extended abstract). In: TLCA'99, Lecture Notes in Computer Science, vol. 1581, Springer, 213–227.Google Scholar
Laurent, O. (March 2002) Etude de la polarisation en logique. Thèse de doctorat, Université Aix-Marseille II.Google Scholar
Laurent, O. (January 2003) Polarized proof-nets and λμ-calculus. Theoretical Computer Science 290 (1) 161–188.Google Scholar
Laurent, O. (December 2004) Polarized games. Annals of Pure and Applied Logic 130 (1–3) 79–123.Google Scholar
Laurent, O. (October 2005) Syntax vs. semantics: A polarized approach. Theoretical Computer Science 343 (1–2) 177–206.Google Scholar
Laurent, O. (2008) Theorie de la demonstration. Cours du Master MPRI.Google Scholar
Laurent, O. and Regnier, L. (2003) About translations of classical logic into polarized linear logic. In: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, 1IEEE Computer Society Press, 1–20.Google Scholar
Melliès, P.-A. (2004) Asynchronous games 2: The true concurrency of innocence. In: CONCUR 04, Lecture Notes in Computer Science, vol. 3170, Springer Verlag.Google Scholar
Melliès, P.-A. (2005) Asynchronous games 4: A fully complete model of propositional linear logic. In: LICS, 386–395.Google Scholar
Melliès, P.-A. and Mimram, S. (2007) Asynchronous games: Innocence without alternation. In: CONCUR, 395–411.Google Scholar
Miller, D. (December 1995) A survey of linear logic programming. In: Computational Logic: The Newsletter of the European Network in Computational Logic, vol. 2.Google Scholar
Pagani, M. (2006) Acyclicity and coherence in multiplicative and exponential linear logic. In: CSL'06, Lecture Notes in Computer Science, vol. 4207, Springer, 531–545.Google Scholar
Pagani, M. and Tortora de Falco, L. (2010) Strong normalization property for second order linear logic. Theoretical Computer Science 411 410–444.Google Scholar
Terese (2003) Term Rewriting Systems, Cambridge Tracts in Theoretical Computer Science, vol. 55, Cambridge University Press.Google Scholar
Terui, K. (2011) Computational ludics. Theoretical Computer Science, 412 (20), 2048–2071.Google Scholar
Tortora de Falco, L. (January 2000) Réseaux, cohérence et expériences obsessionnelles. Thèse de doctorat, Université Paris VII. Available at: http://www.logique.jussieu.fr/www.tortora/index.html.Google Scholar