Abstract
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 PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Lambek, “The mathematics of sentence structure,” Am. Math. Month., 65, No. 3, 154–170 (1958).
A. E. Pentus and M. R. Pentus, “The atomic theory of left division of two-sided ideals of semirings with unit,” Fund. Prikl. Mat., 17, No. 5, 129–146 (2011/2012).
A. E. Pentus and M. R. Pentus, “Proof nets for the Lambek calculus with one division and a negative-polarity modality for weakening,” Fund. Prikl. Mat., 23, No. 2, 247–257 (2020).
Y. Savateev, “Recognition of derivability for the Lambek calculus with one division,” Moscow Univ. Math. Bull., 64, No. 2, 73–75 (2009).
Y. Savateev, “An application of proof-nets to the study of fragments of the Lambek calculus,” Izv. Math., 75, No. 3, 631–663 (2011).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 23, No. 4, pp. 143–162, 2021.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Pentus, A.E., Pentus, M.R. Complexity of the Lambek Calculus with One Division and a Negative-Polarity Modality for Weakening. J Math Sci 269, 544–557 (2023). https://doi.org/10.1007/s10958-023-06299-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-023-06299-z