paper

Complexity of the Infinitary Lambek Calculus with Kleene Star

arXiv:2005.00404 · doi:10.1017/S1755020320000209

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 -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).

arXiv commentManuscript accepted to the Review of Symbolic Logic. An updated version will be published by Cambridge University Press

References in corpus (1)

Cited by in corpus (1)