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/

[1] Lambek I., “Matematicheskoe issledovanie struktury predlozheniya”, Matematicheskaya lingvistika, Sb. perevodov, eds. Yu. A. Shreider i dr., Mir, M., 1964, 47–68

[2] Pentus A. E., Pentus M. R., “Atomarnaya teoriya levogo deleniya dvustoronnikh idealov polukolets s edinitsei”, Fundament. i prikl. mat., 17:5 (2011/2012), 129–146

[3] Pentus A. E., Pentus M. R., “Seti dokazatelstva dlya ischisleniya Lambeka s odnim deleniem i modalnostyu dlya oslableniya, ispolzuemoi tolko pri otritsatelnoi polyarnosti”, Fundament. i prikl. mat., 23:2 (2020), 247–257

[4] Savateev Yu. V., “Raspoznavanie vyvodimosti dlya ischisleniya Lambeka s odnim deleniem”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 2009, no. 2, 59–62 | Zbl

[5] Savateev Yu. V., “Primenenie setei dokazatelstv dlya issledovaniya fragmentov ischisleniya Lambeka”, Izv. RAN. Ser. mat., 75:3 (2011), 189–222 | MR | Zbl