Fundamentalʹnaâ i prikladnaâ matematika, Tome 23 (2021) no. 4, pp. 143-162
Citer cet article
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/
@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},
year = {2021},
volume = {23},
number = {4},
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
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
%U http://geodesic.mathdoc.fr/item/FPM_2021_23_4_a8/
%G ru
%F FPM_2021_23_4_a8
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.
[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
