Geodesic
Complexity of the Lambek calculus with one division and a~negative-polarity modality for weakening
Fundamentalʹnaâ i prikladnaâ matematika, Tome 23 (2021) no. 4, pp. 143-162

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we consider a variant of the Lambek calculus allowing empty antecedents. This variant uses two connectives: the left division and a unary modality that occurs only with negative polarity and allows weakening in antecedents of sequents. We define the notion of a proof net for this calculus, which is similar to those for the ordinary Lambek calculus and multiplicative linear logic. We prove that a sequent is derivable in the calculus under consideration if and only if there exists a proof net for it. We present a polynomial-time algorithm for deciding whether an arbitrary given sequent is derivable in this calculus. 
@article{FPM_2021_23_4_a8,
     author = {A. E. Pentus and M. R. Pentus},
     title = {Complexity of the {Lambek} calculus with one division and a~negative-polarity modality for weakening},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {143--162},
     publisher = {mathdoc},
     volume = {23},
     number = {4},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2021_23_4_a8/}
}
TY  - JOUR
AU  - A. E. Pentus
AU  - M. R. Pentus
TI  - Complexity of the Lambek calculus with one division and a~negative-polarity modality for weakening
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2021
SP  - 143
EP  - 162
VL  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2021_23_4_a8/
LA  - ru
ID  - FPM_2021_23_4_a8
ER  - 
%0 Journal Article
%A A. E. Pentus
%A M. R. Pentus
%T Complexity of the Lambek calculus with one division and a~negative-polarity modality for weakening
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2021
%P 143-162
%V 23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2021_23_4_a8/
%G ru
%F FPM_2021_23_4_a8
A. E. Pentus; M. R. Pentus. Complexity of the Lambek calculus with one division and a~negative-polarity modality for weakening. Fundamentalʹnaâ i prikladnaâ matematika, Tome 23 (2021) no. 4, pp. 143-162. http://geodesic.mathdoc.fr/item/FPM_2021_23_4_a8/