Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T23:25:17.506Z Has data issue: false hasContentIssue false
  • English
  • Français

Deep inference and expansion trees for second-order multiplicative linear logic

Published online by Cambridge University Press:  02 November 2018

LUTZ STRAßBURGER
LUTZ STRAßBURGER*
Affiliation:
Inria Saclay – Île-de-France, 1 rue Honoré d’Estienne d’Orves, Bâtiment Alan Turing, Campus de l’École Polytechnique, 91120 Palaiseau, France Email: lutz@lix.polytechnique.fr
Rights & Permissions [Opens in a new window]

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.

In this paper, we introduce the notion of expansion tree for linear logic. As in Miller's original work, we have a shallow reading of an expansion tree that corresponds to the conclusion of the proof, and a deep reading which is a formula that can be proved by propositional rules. We focus our attention to MLL2, and we also present a deep inference system for that logic. This allows us to give a syntactic proof to a version of Herbrand's theorem.

References

Andrews, P.B. (1976). Refutations by matings. IEEE Transactions on Computers C–25 (8) 801–807.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 Notes, vol. 222, Cambridge University Press, 249–270.CrossRefGoogle Scholar
Blute, R.F., Cockett, J.R.B., Seely, R.A.G. and Trimble, T.H. (1996). Natural deduction and coherence for weakly distributive categories. Journal of Pure and Applied Algebra 113 (3) 229–296.CrossRefGoogle Scholar
Brünnler, K. (2003). Deep Inference and Symmetry for Classical Proofs. PhD thesis, Technische Universität Dresden.Google Scholar
Brünnler, K. and Tiu, A.F. (2001). A local system for classical logic. In: Nieuwenhuis, R. and Voronkov, A. (eds.) Logic for Programming, Artificial Intelligence and Reasoning, LNAI, vol. 2250, Springer, 347–361.CrossRefGoogle Scholar
Buss, S.R. (1991). The undecidability of k-provability. Annals of Pure and Applied Logic 53 (1) 72–102.CrossRefGoogle Scholar
Chaudhuri, K., Guenot, N. and Straßburger, L. (2011). The focused calculus of structures. In: Bezem, M. (ed.) Computer Science Logic, LIPIcs, vol. 12, Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 159–173.Google Scholar
Danos, V. and Regnier, L. (1989). The structure of multiplicatives. Annals of Mathematical Logic 28 (3) 181–203.CrossRefGoogle Scholar
Devarajan, H., Hughes, D., Plotkin, G. and Pratt, V.R. (1999). Full completeness of the multiplicative linear logic of Chu spaces. In: Proceedings of the 14th IEEE Symposium on Logic in Computer Science.Google Scholar
Girard, J.-Y. (1987). Linear logic. Theoretical Computer Science 50 1–102.CrossRefGoogle Scholar
Girard, J.-Y. (1990). Quantifiers in linear logic II. Preépublication de l'Equipe de Logique, Université Paris VII, Nr. 19.Google Scholar
Guglielmi, A. (2007). A system of interaction and structure. ACM Transactions on Computational Logic 8 (1) 1–64.CrossRefGoogle Scholar
Guglielmi, A. and Gundersen, T. (2008). Normalisation control in deep inference via atomic flows. Logical Methods in Computer Science 4 (1:9) 1–36.CrossRefGoogle Scholar
Guglielmi, A. and Straßburger, L. (2001). Non-commutativity and MELL in the calculus of structures. In: Fribourg, L. (ed.) Computer Science Logic, Lecture Notes in Computer Science, vol. 2142, Springer-Verlag, 54–68.CrossRefGoogle Scholar
Guglielmi, A. and Straßburger, L. (2011). A system of interaction and structure V: The exponentials and splitting. Mathematical Structures in Computer Science 21 (3) 563–584.CrossRefGoogle Scholar
Heijltjes, W. and Houston, R. (2014). No proof nets for MLL with units: Proof equivalence in MLL is pspace-complete. In: Henzinger, T.A. and Miller, D. (eds.) Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Vienna, Austria, July 14–18, 2014, 50:1–50:10.Google Scholar
Heijltjes, W. and Hughes, D. J. D. (2015). Complexity bounds for sum-product logic via additive proof nets and petri nets. In: Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE Computer Society, 80–91.CrossRefGoogle Scholar
Hughes, D. J. D. (2012). Simple free star-autonomous categories and full coherence. Journal of Pure and Applied Algebra 216 (11) 2386–2410.CrossRefGoogle Scholar
Hughes, D. J. D. (2018). Unification nets: canonical proof net quantifiers. In: Dawar, A. and Grädel, E. (eds.) Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 9–12, 2018, ACM, 540–549.Google Scholar
Hughes, D. and van Glabbeek, R. (2003). Proof nets for unit-free multiplicative-additive linear logic. In: Proceedings of the 18th IEEE Symposium on Logic in Computer Science, 1–10.Google Scholar
Lafont, Y. (1988). Logique, Catégories et Machines. PhD thesis, Université Paris 7.Google Scholar
Lafont, Y. (1995). From proof nets to interaction nets. In: Girard, J.-Y., Lafont, Y. and Regnier, L. (eds.) Advances in Linear Logic, London Mathematical Society Lecture Notes, vol. 222, Cambridge University Press, 225–247.CrossRefGoogle Scholar
Lamarche, F. and Straßburger, L. (2006). From proof nets to the free *-autonomous category. Logical Methods in Computer Science 2 (4:3) 1–44.CrossRefGoogle Scholar
Lyaletski, A. and Konev, B. (2006). On Herbrand's theorem for intuitionistic logic. In: Fisher, M., van der Hoek, W., Konev, B. and Lisitsa, A. (eds.) Logics in Artificial Intelligence: 10th European Conference, JELIA 2006 Liverpool, UK, Springer, Berlin, Heidelberg, 293–305.CrossRefGoogle Scholar
Miller, D. (1987). A compact representation of proofs. Studia Logica 46 (4) 347–370.CrossRefGoogle Scholar
Retoré, C. (1993). Réseaux et Séquents Ordonnés. PhD thesis, Université Paris VII.Google Scholar
Straßburger, L. (2003). Linear Logic and Noncommutativity in the Calculus of Structures. PhD thesis, Technische Universität Dresden.Google Scholar
Straßburger, L. (2009). Some observations on the proof theory of second order propositional multiplicative linear logic. In: Curien, P.-L. (ed.) Typed Lambda Calculi and Applications, Lecture Notes in Computer Science, vol. 5608, Springer, 309–324.CrossRefGoogle Scholar
Straßburger, L. (2011). From deep inference to proof nets via cut elimination. Journal of Logic and Computation 21 (4) 589–624.CrossRefGoogle Scholar
Straßburger, L. (2017). Deep Inference, Expansion Trees, and Proof Graphs for Second Order Propositional Multiplicative Linear Logic. Research Report RR-9071, Inria Saclay.Google Scholar
Straßburger, L. and Guglielmi, A. (2011). A system of interaction and structure IV: The exponentials and decomposition. ACM Transactions on Computational Logic 12 (4) 23.Google Scholar
Straßburger, L. and Lamarche, F. (2004). On proof nets for multiplicative linear logic with units. In: Marcinkowski, J. and Tarlecki, A. (eds.) Computer Science Logic, Lecture Notes in Computer Science, vol. 3210, Springer-Verlag, 145–159.CrossRefGoogle Scholar
Tubella, A.A. (2016). A study of normalisation through subatomic logic. PhD thesis, University of Bath.Google Scholar