ﻻ يوجد ملخص باللغة العربية
We consider the Lambek calculus, or non-commutative multiplicative intuitionistic linear logic, extended with iteration, or Kleene star, axiomatised by means of an $omega$-rule, and prove that the derivability problem in this calculus is $Pi_1^0$-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 Lambeks non-emptiness restriction imposed (cf. Safiullin 2007).
We investigate language interpretations of two extensions of the Lambek calculus: with additive conjunction and disjunction and with additive conjunction and the unit constant. For extensions with additive connectives, we show that conjunction and di
Formulae of the Lambek calculus are constructed using three binary connectives, multiplication and two divisions. We extend it using a unary connective, positive Kleene iteration. For this new operation, following its natural interpretation, we prese
The Lambek calculus is a well-known logical formalism for modelling natural language syntax. The original calculus covered a substantial number of intricate natural language phenomena, but only those restricted to the context-free setting. In order t
This paper shows connections between command injection attacks, continuations, and the Lambek calculus: certain command injections, such as the tautology attack on SQL, are shown to be a form of control effect that can be typed using the Lambek calcu
We present a translation of the Lambek calculus with brackets and the unit constant, $mathbf{Lb}^{boldsymbol{*}}_{mathbf{1}}$, into the Lambek calculus with brackets allowing empty antecedents, but without the unit constant, $mathbf{Lb}^{boldsymbol{*