[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Lambek Calculus with Banged Atoms for Parasitic Gaps

  • Conference paper
  • First Online:
Logic, Language, Information, and Computation (WoLLIC 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14672))

  • 156 Accesses

Abstract

Lambek Calculus is a non-commutative substructural logic for formalising linguistic constructions. However, its domain of applicability is limited to constructions with local dependencies. We propose here a simple extension that allows us to formalise a range of relativised constructions with long distance dependencies, notably medial extractions and the challenging case of parasitic gaps. In proof theoretic terms, our logic combines commutative and non-commutative behaviour, as well as linear and non-linear resource management. This is achieved with a single restricted modality. But unlike other extensions of Lambek Calculus with modalities, our logic remains decidable, and the complexity of proof search (i.e., sentence parsing) is the same as for the basic Lambek calculus. Furthermore, we provide not only a sequent calculus, and a cut elimination theorem, but also proof nets.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 49.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 64.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    Note that we do not have weakening. This has linguistic reasons as well as proof theoretical reasons [10].

  2. 2.

    We thank an anonymous referee for this simplification. However, if the reader insists on a system with only atomic \(\textsf{id}\)-rules, then can be replaced by , yielding an equivalent system, not affecting any of the results in this paper.

  3. 3.

    Observe that since we only allow atoms under the \(\mathord !\), we do not have the issue discussed in [17].

  4. 4.

    Note that even though the language is similar to cyclic MELL, the logic is very different.

  5. 5.

    Note the inversion of the order of the arguments, which is crucial.

  6. 6.

    There is only one \(\mathsf {perm_{}}\)-rule in \(\mathsf {CyMLL_{!?}}\) because the other one is derivable with the help of the \(\textsf{cyc}\)-rule.

  7. 7.

    Here we also invert the order, even though this is not strictly needed (and also not done in [20]). We do it here to ease the use of the system for the linguistic applications.

  8. 8.

    Furthermore, the order of the formulas in the conclusion is the same in the two derivations in Examples 2.3 and 4.3. This is the reason for inverting the order in the definition of \((\cdot )^\flat \).

  9. 9.

    To simplify the presentation, we consider the modalities not as unary inner nodes, but as part of the leaves.

  10. 10.

    Note that we can restrict the number of consecutive applications of the \(\textsf{cyc}\)- and \(\mathsf {perm_{}}\)-rules.

References

  1. Abrusci, V.M., Ruet, P.: Non-commutative logic I: the multiplicative fragment. Ann. Pure Appl. Logic 101, 29–64 (2000)

    Article  MathSciNet  Google Scholar 

  2. Barry, G., Hepple, M., Leslie, N., Morrill, G.: Proof figures and structural operators for categorial grammar. In: Kunze, J., Reimann, D. (eds.) EACL 1991, 5th Conference of the European Chapter of the Association for Computational Linguistics, 9–11 April 1991, Congress Hall, Alexanderplatz, Berlin, Germany, pp. 198–203. The Association for Computer Linguistics (1991)

    Google Scholar 

  3. Culicover, P., Postal, P. (eds.): Parasitic Gaps. MIT Press, Cambridge (2001)

    Google Scholar 

  4. Danos, V., Regnier, L.: The structure of multiplicatives. Arch. Math. Log. 28(3), 181–203 (1989)

    Article  MathSciNet  Google Scholar 

  5. Engdahl, E.: Parasitic gaps. Linguist. Philos. 6(1), 5–34 (1983)

    Article  Google Scholar 

  6. Girard, J.-Y.: Linear logic. Theoret. Comput. Sci. 50, 1–102 (1987)

    Article  MathSciNet  Google Scholar 

  7. Girard, J.-Y.: On the unity of logic. Ann. Pure Appl. Logic 59, 201–217 (1993)

    Article  MathSciNet  Google Scholar 

  8. Guglielmi, A.: A system of interaction and structure. ACM Trans. Comput. Logic 8(1), 1–64 (2007)

    Article  MathSciNet  Google Scholar 

  9. Guglielmi, A., Straßburger, L.: Non-commutativity and MELL in the calculus of structures. In: Fribourg, L. (ed.) CSL 2001. LNCS, vol. 2142, pp. 54–68. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44802-0_5

    Chapter  Google Scholar 

  10. Heijltjes, W., Houston, R.: Proof equivalence in MLL is PSPACE-complete. Log. Methods Comput. Sci. 12(1) (2016)

    Google Scholar 

  11. Jäger, G.: Anaphora and Type Logical Grammar, vol. 24. Springer, Dordrecht (2006). https://doi.org/10.1007/1-4020-3905-0

    Book  Google Scholar 

  12. Kanazawa, M.: The lambek calculus enriched with additional connectives. J. Logic Lang. Inform. 1(2), 141–171 (1992)

    Article  MathSciNet  Google Scholar 

  13. Kanovich, M.I., Kuznetsov, S.L., Nigam, V., Scedrov, A.: Subexponentials in non-commutative linear logic. Math. Struct. Comput. Sci. 29(8), 1217–1249 (2019)

    Article  MathSciNet  Google Scholar 

  14. Kanovich, M., Kuznetsov, S., Nigam, V., Scedrov, A.: Soft subexponentials and multiplexing. In: Peltier, N., Sofronie-Stokkermans, V. (eds.) IJCAR 2020. LNCS (LNAI), vol. 12166, pp. 500–517. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51074-9_29

    Chapter  Google Scholar 

  15. Kanovich, M., Kuznetsov, S., Scedrov, A.: Undecidability of the lambek calculus with a relevant modality. In: Foret, A., Morrill, G., Muskens, R., Osswald, R., Pogodalla, S. (eds.) FG 2015-2016. LNCS, vol. 9804, pp. 240–256. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53042-9_14

    Chapter  Google Scholar 

  16. Kanovich, M., Kuznetsov, S., Scedrov, A.: Undecidability of the lambek calculus with subexponential and bracket modalities. In: Klasing, R., Zeitoun, M. (eds.) FCT 2017. LNCS, vol. 10472, pp. 326–340. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-55751-8_26

    Chapter  Google Scholar 

  17. Kanovich, M.I., Kuznetsov, S.L., Scedrov, A.: Reconciling lambek’s restriction, cut-elimination and substitution in the presence of exponential modalities. J. Log. Comput. 30(1), 239–256 (2020)

    Article  MathSciNet  Google Scholar 

  18. Kogkalidis, K., Moortgat, M., Moot, R.: Æthel: automatically extracted typelogical derivations for Dutch. In: Calzolari, N., et al. (eds.) Proceedings of The 12th Language Resources and Evaluation Conference, LREC 2020, Marseille, France, 11–16 May 2020, pp. 5257–5266. European Language Resources Association (2020)

    Google Scholar 

  19. Kogkalidis, K., Moortgat, M., Moot, R.: SPINDLE: spinning raw text into lambda terms with graph attention. In: Croce, D., Soldaini, L. (eds.) Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics. EACL 2023 - System Demonstrations, Dubrovnik, Croatia, 2–4 May 2023, pp. 128–135. Association for Computational Linguistics (2023)

    Google Scholar 

  20. Lamarche, F., Retoré, C.: Proof nets for the Lambek-calculus — an overview. In: Michele Abrusci, V., Casadio, C. (eds.) Proceedings of the Third Roma Workshop “Proofs and Linguistic Categories”, pp. 241–262. CLUEB, Bologna (1996)

    Google Scholar 

  21. Lambek, J.: The mathematics of sentence structure. Am. Math. Monthly 65, 154–170 (1958)

    Article  MathSciNet  Google Scholar 

  22. Lazić, R., Schmitz, S.: Nonelementary complexities for branching VASS, MELL, and extensions. ACM Trans. Comput. Logic 16(3), 1–30 (2015)

    Article  MathSciNet  Google Scholar 

  23. Mcpheat, L., Wijnholds, G., Sadrzadeh, M., Correia, A., Toumi, A.: Anaphora and ellipsis in lambek calculus with a relevant modality: Syntax and semantics. J. Cogn. Sci. 22, 1–34 (2021)

    Google Scholar 

  24. Moortgat, M.: Multimodal linguistic inference. J. Logic Lang. Inform. 5(3–4), 349–385 (1996)

    Article  MathSciNet  Google Scholar 

  25. Moortgat, M., Oehrle, R.: Structural abstractions. In: Proofs and Linguistic Categories: Application of Logic to the Analysis and Implementation of Natural Language, Proceedings of the 1996 Roma Workshop (1996)

    Google Scholar 

  26. Moortgat, M., Sadrzadeh, M., Wijnholds, G.: A frobenius algebraic analysis for parasitic gaps. FLAP 7(5), 823–852 (2020)

    MathSciNet  Google Scholar 

  27. Moortgat, M., Sadrzadeh, M., Wijnholds, G.: A frobenius algebraic analysis for parasitic gaps. J. Appl. Log. 7, 823–852 (2020)

    MathSciNet  Google Scholar 

  28. Moot, R.: Semi-automated extraction of a wide-coverage type-logical grammar for French. In: Langlais, P., Gagnon, M. (eds.) Actes de la 17e conférence sur le Traitement Automatique des Langues Naturelles. Articles courts, TALN 2010, Montréal, Canada, July 2010, pp. 189–194. ATALA (2010)

    Google Scholar 

  29. Moot, R.: The grail theorem prover: type theory for syntax and semantics. CoRR, abs/1602.00812 (2016)

    Google Scholar 

  30. Moot, R., Puite, Q.: Proof nets for the multimodal lambek calculus. Stud. Logica. 71, 415–442 (2002)

    Article  MathSciNet  Google Scholar 

  31. Morrill, G., Leslie, N., Hepple, M., Barry, G.: Categorial deductions and structural operations. Studies in Categorial Grammar. Edinburgh Working Papers in Cognitive Science (1990)

    Google Scholar 

  32. Morrill, G., Valentín, O.: Computational coverage of TLG: Nonlinearity. In: Proceedings of Third Workshop on Natural Language and Computer Science, vol. 32, pp. 51–63. EasyChair Publications (2015)

    Google Scholar 

  33. Morrill, G., Valentín, O.: On the logic of expansion in natural language. In: Amblard, M., de Groote, P., Pogodalla, S., Retoré, C. (eds.) LACL 2016. LNCS, vol. 10054, pp. 228–246. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53826-5_14

    Chapter  Google Scholar 

  34. Morrill, G., Valentín, O., Fadda, M.: The displacement calculus. J. Logic Lang. Inform. 20(1), 1–48 (2011)

    Article  MathSciNet  Google Scholar 

  35. Nigam, V., Miller, D.: Algorithmic specifications in linear logic with subexponentials. In: ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP), pp. 129–140 (2009)

    Google Scholar 

  36. Oehrle, R.T.: Resource-sensitivity–a brief guide. In: Kruijff, G.-J.M., Oehrle, R.T. (eds.) Resource-Sensitivity, Binding and Anaphora, pp. 231–255. Springer, Dordrecht (2003). https://doi.org/10.1007/978-94-010-0037-6_9

    Chapter  Google Scholar 

  37. Pentus, M.: Lambek calculus is np-complete. Theor. Comput. Sci. 357(1–3), 186–201 (2006)

    Article  MathSciNet  Google Scholar 

  38. Retoré, C.: Pomset logic: a non-commutative extension of classical linear logic. In: de Groote, P., Roger Hindley, J. (eds.) TLCA 1997. LNCS, vol. 1210, pp. 300–318. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62688-3_43

    Chapter  Google Scholar 

  39. Straßburger, L.: System NEL is undecidable. In: De Queiroz, R., Pimentel, E., Figueiredo, L. (eds.) 10th Workshop on Logic, Language, Information and Computation (WoLLIC). Electronic Notes in Theoretical Computer Science, vol. 84, pp. 166–177 (2003)

    Google Scholar 

  40. Yetter, D.N.: Quantales and (noncommutative) linear logic. J. Symb. Log. 55(1), 41–64 (1990)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University College London, London, UK

    Mehrnoosh Sadrzadeh

  2. INRIA Saclay, Ile-de-France, Palaiseau, France

    Lutz Straßburger

Authors
  1. Mehrnoosh Sadrzadeh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lutz Straßburger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mehrnoosh Sadrzadeh .

Editor information

Editors and Affiliations

  1. University of Bern, Bern, Switzerland

    George Metcalfe

  2. University of Bern, Bern, Switzerland

    Thomas Studer

  3. Federal University of Pernambuco, Recife, Brazil

    Ruy de Queiroz

A Appendix

A Appendix

Let us first show the full proof tree of (c) “articles that reviewers accepted after skimming without reading”, and the resulting proof net:

figure ad
figure ae

In order to model (e) and (f) we need new atoms. We use the atoms used in [27] for adjective phrases and infinitives of verbs. A few shortcuts are also implemented to keep the size of the proof trees manageable. For instance instead of typing “a” separately and “review” and “blog post” separately, we assign the type n to “a review”, similarly to “a blog post” in one step. The new assignments are presented below:

(5)

Here are the proof tree and proof net for (d) “articles that chairs persuaded every reviewer of to accept”:

figure af
figure ag

Finally, here are the proof tree and prof net for (e) “articles that a review about in a blog post made famous”:

figure ah
figure ai

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Sadrzadeh, M., Straßburger, L. (2024). Lambek Calculus with Banged Atoms for Parasitic Gaps. In: Metcalfe, G., Studer, T., de Queiroz, R. (eds) Logic, Language, Information, and Computation. WoLLIC 2024. Lecture Notes in Computer Science, vol 14672. Springer, Cham. https://doi.org/10.1007/978-3-031-62687-6_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-62687-6_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-62686-9

  • Online ISBN: 978-3-031-62687-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation