2016/08/13 by Max Kanovich, Kanovich, Max, Stepan Kuznetsov +3
Computer Science · #03B47 #Computation and Language (cs.CL) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Natural Language Processing Techniques
paper · pdf · doi:10.48550/arxiv.1608.04020
openalex publication_date 2016/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Lambek calculus is a well-known logical formalism for modelling natural\nlanguage syntax. The original calculus covered a substantial number of\nintricate natural language phenomena, but only those restricted to the\ncontext-free setting. In order to address more subtle linguistic issues, the\nLambek calculus has been extended in various ways. In particular, Morrill and\nValentin (2015) introduce an extension with so-called exponential and bracket\nmodalities. Their extension is based on a non-standard contraction rule for the\nexponential that interacts with the bracket structure in an intricate way. The\nstandard contraction rule is not admissible in this calculus. In this paper we\nprove undecidability of the derivability problem in their calculus. We also\ninvestigate restricted decidable fragments considered by Morrill and Valentin\nand we show that these fragments belong to the NP class.\n