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

      Complexity of the Infinitary Lambek Calculus with Kleene Star

      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 consider the Lambek calculus, or non-commutative multiplicative intuitionistic linear logic, extended with iteration, or Kleene star, axiomatised by means of an ω-rule, and prove that the derivability problem in this calculus is Π01-hard. This solves a problem left open by Buszkowski (2007), who obtained the same complexity bound for infinitary action logic, which additionally includes additive conjunction and disjunction. As a by-product, we prove that any context-free language without the empty word can be generated by a Lambek grammar with unique type assignment, without Lambek's non-emptiness restriction imposed (cf. Safiullin 2007).

          Related collections

          Author and article information

          Journal
          01 May 2020
          Article
          2005.00404
          422f896e-0c40-4c39-b5ac-43151d458e7d

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

          History
          Custom metadata
          Manuscript accepted to the Review of Symbolic Logic. An updated version will be published by Cambridge University Press
          math.LO cs.LO

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

          Comments

          Comment on this article