[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Non-Commutative Linear Logic in Linguistics

  • Published:
Grammars

Abstract

This paper explores the linguistic implications of Non-commutative Linear Logic, with particular reference to its multiplicative fragment MNLL, that exhibits a direct relationship to Lambek's Syntactic Calculus. Such a framework is appealing for linguistic analysis since it allows one to develop a dynamic characterization of the notion of a function, that plays a basic role in the foundations of categorial grammar. The analysis will focus on a variety of constructions involving scope configurations, unbounded dependencies and Wh-clauses. Particular attention is given to the proof nets for MNLL, that are planar graphs in which the communication processes and the flow of information are represented by means of a parallelistic architecture. We will introduce proof nets and sequent derivations associated to each linguistic expression and will show that a direct relationship exists between the types and derivations of the Syntactic Calculus and the corresponding types and derivations in MNLL. Moreover, given the symmetric architecture and the crucial role played by the two negations of Non-commutative Linear Logic in the generation of the logical types, we will show that this system is richer in expressive power and in the capacity of performing left-to-right computations of word strings.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Abrusci, V. M. Phase semantics and sequent calculus for pure noncommutative classical linear propositional logic, The Journal of Symbolic Logic, 56: 1403–1451, 1991.

    Google Scholar 

  • Abrusci, V. M. Noncommutative proof nets. In Girard et al., editors, Advances in Linear Logic, 271–296, Cambridge University Press, Cambridge, 1995.

    Google Scholar 

  • Abrusci, V. M. Lambek calculus, cyclic multiplicative-additive linear logic, noncommutative multiplicative-additive linear logic: language and sequent calculus. In V. M. Abrusci and C. Casadio, editors, Proofs and Linguistic Categories. Applications of Logic to the Analysis and Implementation of Natural Language, 21–48, CLUEB, Bologna, 1996.

    Google Scholar 

  • Abrusci, V. M. and E. Maringelli, A new correctness criterion for cyclic proof nets, The Journal of Logic, Language and Information, 7: 449–459, 1998.

    Google Scholar 

  • Abrusci, V. M. and Ruet, P. Non-commutative logic I: the multiplicative fragment, Annals of Pure and Applied Logic, 101: 29–64, 2000.

    Google Scholar 

  • Ajdukiewicz, K. Die Syntaktische Konnexität, Studia Philosophica, 1: 1–27, 1935. Eng trans, Syntactic connexion. In McCall, editor, 1967.

  • Bar-Hillel, Y. A quasi-arithmetical notation for syntactic description, Language, 29: 47–58, 1953. Repr. in Y. Bar-Hillel, editor, Language and Information, 61–74, Palo Alto, 1964.

    Google Scholar 

  • Barr, M. Autonomous categories revisited, Journal of Pure and Applied Algebra, 111: 1–20, 1996.

    Google Scholar 

  • Benthem, J. van. Essays in Logical Semantics, Reidel, Dordrecht, 1986.

    Google Scholar 

  • Benthem, J. van. The Lambek calculus. In R. T. Oehrle et al., editors, Categorial Grammars and Natural Language Structures, Reidel, Dordrecht, 35–68, 1988.

    Google Scholar 

  • Benthem, J. van. Language in Action, North-Holland, Amsterdam, 1991.

    Google Scholar 

  • Benthem, J. van and A. ter Meulen, editors. Handbook of Logic and Language, Elsevier, Amsterdam, 1997.

    Google Scholar 

  • Buszkowski, W. Lambek's Categorial Grammars, Institute of Mathematics, Adam Mickiewicz University, Poznań, 1982.

    Google Scholar 

  • Buszkowski, W. The equivalence of unidirectional Lambek categorial grammars and context free grammars, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 31: 308–384, 1985.

    Google Scholar 

  • Buszkowski, W., W. Marciszewski and J. van Benthem, editors. Categorial Grammar, John Benjamins, Amsterdam, 1990.

    Google Scholar 

  • Carpenter, B. Type-Logical Semantics, The MIT Press, Cambridge, MA, 1998.

    Google Scholar 

  • Casadio, C. Semantic categories and the development of categorial grammars. In R. T. Oehrle et al., editors, Categorial Grammars and Natural Language Structures, 95–123, Reidel, Dordrecht, 1988.

    Google Scholar 

  • Casadio, C. Unbounded dependencies in non-commutative linear logic. In Proceedings of the Conference on Formal Grammar, ESSLLI, Aix-en-Provence, 1997.

    Google Scholar 

  • Casadio, C, and J, Lambek. An algebraic analysis of clitic pronouns in Italian. In P. de Groote, G. Morrill and C. Retoré, editors, Logical Aspects of Computational Linguistics, 110–124, Springer, Berlin, 2001.

    Google Scholar 

  • Casadio, C. and J. Lambek. A tale of four grammars, Studia Logica, to appear.

  • Cockett, J. R. B. and R. A. G. Seely. Proof theory for full intuitionistic linear logic, bilinear logic, and MIX categories, Theory and Applications of Categories, 3/5: 85–131, 1997.

    Google Scholar 

  • Frege, G. Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens, L. Nebert, Halle, 1879. Translated by S. Bauer-Mengelberg as Begriffsschrift, a formula language, modeled upon that of arithmetic, for pure thought. In J. van Heijnoort, editor, From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, Harvard University Press, Cambridge, MA, 1967.

    Google Scholar 

  • Frege, G. Funktion und Begriff, Pole Jena, 1891. In G. Patzig, editor, Funktion, Begriff, Bedeutung, Vandenhoeck und Ruprecht, Göttingen, 1962.

    Google Scholar 

  • Frege, G. Die Grundgesetze der Arithmetik, Pole Jena, 1893–1903; Olms, Hildesheim, 1966.

    Google Scholar 

  • Geach, P. T. A program for syntax. In D. Davidson and G. Harman, editors, Semantics of Natural Language, 483–497, Reidel, Dordrecht, 1972.

    Google Scholar 

  • Girard, J. Y. Linear logic, Theoretical Computer Science, 50: 1–102, 1987.

    Google Scholar 

  • Girard, J. Y. Linear logic: its syntax and semantics, In J. Y. Girard et al., editors, Advances in Linear Logic, 1–42, Cambridge University Press, Cambridge, 1995.

    Google Scholar 

  • Husserl, E. Logische Untersuchungen, Max Niemeyer, Halle, 1922. Rev. ed. Martinus Nijhoff, The Hague, 1984.

    Google Scholar 

  • Johnson, M. Proof nets and the complexity of processing center embedded constructions. Journal of Logic, Language and Information, 7: 433–447, 1998.

    Google Scholar 

  • Lamarche, F. and C. Retoré. Proof nets for the Lambek calculus — an overview, In Proofs and Linguistic Categories: Proceedings of the 1996 Roma Workshop, 241–262, CLUEB, Bologna, 1996.

    Google Scholar 

  • Lambek, J. The mathematics of sentence structure, American Mathematical Monthly, 65: 154–170, 1958.

    Google Scholar 

  • Lambek, J. From categorial grammar to bilinear logic. In K. Došen et al., editors, Substructural Logics, Oxford University Press, Oxford, 1993.

    Google Scholar 

  • Lambek, J. Bilinear logic in algebra and linguistics. In J. Y. Girard et al., editors, Advances in Linear Logic, 43–60, Cambridge University Press, Cambridge, 1995.

    Google Scholar 

  • Lambek, J. Cut elimination for classical bilinear logic, Fundamenta Informaticae, 22: 55–67, 1995.

    Google Scholar 

  • Lambek, J. Type grammars revisited. In A. Lecomte, F. Lamarche and G. Perrier, editors, Logical Aspects of Computational Linguistics, Springer, Berlin 1582, 1–27, 1999.

    Google Scholar 

  • Lambek, J. Pregroups: a new algebraic approach to sentence structure. In C. Martín-Vide and G. Păun, editors, Recent Topics in Mathematical and Computational Linguistics, Editura Academiei Române, Bucharest, 2000.

    Google Scholar 

  • Lambek, J. and P.J. Scott. Introduction to Higher Order Categorial Logic, Cambridge University Press, Cambridge, 1986.

    Google Scholar 

  • Lecomte, A. and C. Retoré. Pomset logic as an alternative to categorial grammar. In Proceedings of the Conference on Formal Grammar, ESSLLI, Barcelona, 1995.

    Google Scholar 

  • McCall, S., editor. Polish Logic, Clarendon, Oxford, 1967.

    Google Scholar 

  • Moortgat, M. Categorial Investigations. Logical and Linguistic Aspects of the Lambek Calculus, Foris, Dordrecht, 1988.

    Google Scholar 

  • Moortgat, M. Categorial type logics. In J. van Benthem and A. ter Meulen, editors, 93–177, 1997.

  • Morrill, G. Type Logical Grammar, Kluwer, Dordrecht, 1994.

    Google Scholar 

  • Morrill, G. Memoisation of categorial proof nets: parallelism in categorial processing. In V. M. Abrusci and C. Casadio, editors, Proofs and Linguistic Categories. Applications of Logic to the Analysis and Implementation of Natural Language, CLUEB, Bologna, 157–169, 1996.

    Google Scholar 

  • Morrill, G. Incremental processing and acceptability, Report de Recerca LSI-98-46-R, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, 1998.

  • Morrill, G. Relational interpretation and geometrical form. In V. M. Abrusci and C. Casadio, editors, Dynamic Perspectives in Logic and Linguistics, Bulzoni, Roma, 145–182, 1999.

    Google Scholar 

  • Partee, B. H. and H.L.W. Hendriks. Montague grammar, In J. van Benthem and A. ter Meulen, editors, 5–91, 1997.

  • Pentus, M. Lambek grammars are context free, In Proceedings of the Eighth Logic in Computer Science Conference, 429–433, 1993.

  • Pentus, M. Product-free Lambek calculus and context-free grammars, Journal of Symbolic Logic, 62: 648–660, 1997.

    Google Scholar 

  • Retoré, C., editor. Logical Aspects of Computational Linguistics. First International Conference, LACL 96, Springer, Berlin, 1996.

    Google Scholar 

  • Roorda, D. Resource Logics: Proofs Theoretical Investigations, Ph.D. dissertation, Universiteit van Amsterdam, 1991.

  • Yetter, D. N. Quantales and (non-commutative) linear logic, Journal of Symbolic Logic, 55: 41–64, 1990.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Casadio, C. Non-Commutative Linear Logic in Linguistics. Grammars 4, 167–185 (2001). https://doi.org/10.1023/A:1012429728354

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1012429728354

Navigation