8
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      The Multiplicative-Additive Lambek Calculus with Subexponential and Bracket Modalities

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We give a proof-theoretic and algorithmic complexity analysis for systems introduced by Morrill to serve as the core of the CatLog categorial grammar parser. We consider two recent versions of Morrill's calculi, and focus on their fragments including multiplicative (Lambek) connectives, additive conjunction and disjunction, brackets and bracket modalities, and the ! subexponential modality. For both systems, we resolve issues connected with the cut rule and provide necessary modifications, after which we prove admissibility of cut (cut elimination theorem). We also prove algorithmic undecidability for both calculi, and show that categorial grammars based on them can generate arbitrary recursively enumerable languages.

          Related collections

          Author and article information

          Journal
          31 July 2020
          Article
          2008.00075
          81087aed-0342-4178-ab95-78808ad69e13

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          Submitted to the Journal of Logic, Language, and Information
          cs.LO math.LO

          Theoretical computer science,Logic & Foundation
          Theoretical computer science, Logic & Foundation

          Comments

          Comment on this article