?
L-models and R-models for Lambek calculus enriched with additives and the multiplicative unit
P. 373–391.
Language and relational models, or L-models and R-models, are two natural classes of models for the Lambek calculus. Completeness w.r.t. L-models was proved by Pentus and completeness w.r.t. R-models by Andréka and Mikulás. It is well known that adding both additive conjunction and disjunction together yields incompleteness, because of the distributive law. The product-free Lambek calculus enriched with conjunction only, however, is complete w.r.t. L-models (Buszkowski) as well as R-models (Andréka and Mikulás). The situation with disjunction turns out to be the opposite: we prove that the product-free Lambek calculus enriched with disjunction only is incomplete w.r.t. L-models as well as R-models. If the empty premises are allowed, the product-free Lambek calculus enriched with conjunction only is still complete w.r.t. L-models but in which the empty word is allowed. Both versions are decidable (PSPACE-complete in fact). Adding the multiplicative unit to represent explicitly the empty word within the L-model paradigm changes the situation in a completely unexpected way. Namely, we prove undecidability for any L-sound extension of the Lambek calculus with conjunction and with the unit, whenever this extension includes certain L-sound rules for the multiplicative unit, to express the natural algebraic properties of the empty word. Moreover, we obtain undecidability for a small fragment with only one implication, conjunction, and the unit, obeying these natural rules. This proof proceeds by the encoding of two-counter Minsky machines.
In book
Vol. 11541: Lecture Notes in Computer Science. , Berlin, Heidelberg: Springer, 2019.
Stepan L. Kuznetsov, Journal of Logic and Computation 2026 Vol. 36 No. 1 Article exaf078
The linguistic applications of the Lambek calculus suggest its semantics over algebras of formal languages. A straightforward approach to construct such semantics indeed yields a brilliant completeness theorem (Pentus 1995, Ann. Pure Appl. Logic, 75, 179–213). However, extending the calculus with extra operations ruins completeness. In order to mitigate this issue, Wurm (2017, J. Logic Lang. Inf., ...
Added: January 14, 2026
Kuznetsov S., Speranski S. O., Annals of Pure and Applied Logic 2022 Vol. 173 No. 2 Article 103057
We introduce infinitary action logic with exponentiation — that is, the multiplicative-additive Lambek calculus extended with Kleene star and with a family of subexponential modalities, which allow some of the structural rules (contraction, weakening, permutation). The logic is presented in the form of an infinitary sequent calculus. We prove cut elimination and, in the case ...
Added: December 26, 2025
Kuznetsov S., Speranski S. O., Studia Logica 2023 Vol. 111 No. 2 P. 251–280
Infinitary action logic can be naturally expanded by adding exponential and subexponential modalities from linear logic. In this article we shall develop infinitary action logic with a subexponential that allows multiplexing (instead of contraction). Both non-commutative and commutative versions of this logic will be considered, presented as infinitary sequent calculi. We shall prove cut admissibility ...
Added: December 26, 2025
Kuznetsov S., Lugovaya V., Ryzhova A., Logic Journal of the IGPL 2019 Vol. 27 No. 3 P. 252–266
Added: May 1, 2025
Stepan L. Kuznetsov, , in: Logic, Language, Information, and Computation: 30th International Workshop, WoLLIC 2024, Bern, Switzerland, June 10–13, 2024, ProceedingsVol. 14672: Lecture Notes in Computer Science.: Cham: Springer, 2024. P. 93–107.
Added: June 12, 2024
Sergey Slavnov, Logical Methods in Computer Science 2023 Vol. 19 No. 4
It is known that different categorial grammars have surface representation in a fragment of first order multiplicative linear logic (MLL1). We show that the fragment of interest is equivalent to the recently introduced extended tensor type calculus (ETTC). ETTC is a calculus of specific typed terms, which represent tuples of strings, more precisely bipartite graphs ...
Added: December 20, 2023
S. M. Dudakov, Karlov B. N., S. L. Kuznetsov et al., Algebra and Logic 2021 Vol. 60 No. 5 P. 308–326
The Lambek calculus with the unit can be defined as the atomic theory (algebraic logic) of the class of residuated monoids. This calculus, being a theory of a broader class of algebras than Heyting ones, is weaker than intuitionistic logic. Namely, it lacks structural rules: permutation, contraction, and weakening. We consider two extensions of the ...
Added: November 12, 2023
Smetanin S., Mikhail Komarov, PeerJ Computer Science 2022 Vol. 8 Article e1181
As one of the major platforms of communication, social networks have become a valuable source of opinions and emotions. Considering that sharing of emotions offline and online is quite similar, historical posts from social networks seem to be a valuable source of data for measuring observable subjective well-being (OSWB). In this study, we calculated OSWB ...
Added: December 29, 2022
Kanovich M., Kuznetsov Stepan G., Kuznetsov S. et al., Studies in Computational Intelligence 2021 Vol. 999 P. 1–24
CatLog is a categorial grammar parser/theorem-prover
developed by Glyn Morrill and his co-authors. CatLog is based on an
extension of Lambek calculus. A distinctive feature of this extension is
the usage of brackets for controlled non-associativity and a subexponential
modality whose contraction rule interacts with bracketing in a
sophisticated way. We consider two variants of the calculus, appearing in
different versions ...
Added: December 14, 2021
Kanovich M., Kuznetsov S., Scedrov A., Information and Computation 2022 Vol. 287 Article 104760
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 disjunction behave differently. Adding both of them leads to incompleteness due to the distributivity law. We show that with conjunction only ...
Added: December 4, 2021
Slavnov S. A., Journal of Logic and Computation 2022 Vol. 32 No. 3 P. 479–517
We consider tensor grammars, which are an example of ‘commutative’ grammars, based on the classical (rather than intuitionistic) linear logic. They can be seen as a surface representation of abstract categorial grammars (ACG) in the sense that derivations of ACG translate to derivations of tensor grammars and this translation is isomorphic on the level of string ...
Added: October 21, 2021
Rybakov M., Shkatov D., Logic Journal of the IGPL 2022 Vol. 30 No. 3 P. 519–533
We obtain an effective embedding of the classical predicate logic into the logic of partial quasiary predicates. The embedding has the property that an image of a non-theorem of the classical logic is refutable in a model of the logic of partial quasiary predicates that has the same cardinality as the classical countermodel of the ...
Added: May 29, 2021
Lopukhina Anastasia, Pletenev S., Nikiforova A. et al., , in: Proceedings of the Second Workshop on Linguistic and Neurocognitive Resources.: Marseille: European Language Resources Association (ELRA), 2020. P. 28–37.
Linguistics predictability is the degree of confidence in which language unit (word, part of speech, etc.) will be the next in the sequence. Experiments have shown that the correct prediction simplifies the perception of a language unit and its integration into the context. As a result of an incorrect prediction, language processing slows down. Currently, ...
Added: April 20, 2021
Nikolay Arefyev, Sheludko B., Podolskiy A. et al., , in: Proceedings of the 28th International Conference on Computational Linguistics.: International Committee on Computational Linguistics, 2020. P. 1242–1255.
Lexical substitution, i.e. generation of plausible words that can replace a particular target word in a given context, is an extremely powerful technology that can be used as a backbone of various NLP applications, including word sense induction and disambiguation, lexical relation extraction, data augmentation, etc. In this paper, we present a large-scale comparative study ...
Added: December 7, 2020
Malykh V., Chernis K., Artemova E. et al., , in: Proceedings of the 28th International Conference on Computational Linguistics.: International Committee on Computational Linguistics, 2020. Ch. 503 P. 5718–5730.
The existing dialogue summarization corpora are significantly extractive. We introduce a methodology for dataset extractiveness evaluation and present a new low-extractive corpus of movie dialogues for abstractive text summarization along with baseline evaluation. The corpus contains 153k dialogues and consists of three parts: 1) automatically aligned subtitles, 2) automatically aligned scenes from scripts, and 3) ...
Added: December 6, 2020
Kanovich M., Kuznetsov S., Scedrov A., Journal of Logic, Language and Information 2021 Vol. 30 No. 1 P. 31–88
We give a proof-theoretic and algorithmic complexity analysis for systems introduced by Morrill to serve as the core of the CatLog categorial grammar parser. We consider two recent versions of Morrill’s calculi, and focus on their fragments including multiplicative (Lambek) connectives, additive conjunction and disjunction, brackets and bracket modalities, and the ! subexponential modality. For ...
Added: November 25, 2020
Kuznetsov S., , in: Logic, Language, and Security. Essays Dedicated to Andre Scedrov on the Occasion of His 65th BirthdayIssue 12300.: Cham: Springer, 2020. P. 3–16.
Infinitary action logic is an extension of the multiplicative-additive Lambek calculus with Kleene iteration, axiomatized by an 𝜔-rule. Buszkowski and Palka (2007) show that this logic is \(\Pi^0_1\)-complete. As shown recently by Kuznetsov and Speranski, the extension of infinitary action logic with the exponential modality is much harder: \(\Pi^1_1\)-complete. The raise of complexity is of ...
Added: November 25, 2020
Arefyev Nikolay, Sheludko B., Adis D. et al., , in: Proceedings of the 13th International Workshop on Semantic Evaluation (SemEval-2019).: Minneapolis: Association for Computational Linguistics, 2019. P. 31–38.
We describe our solutions for semantic frame and role induction subtasks of SemEval 2019 Task 2. Our approaches got the highest scores, and the solution for the frame induction problem officially took the first place. The main contributions of this paper are related to the semantic frame induction problem. We propose a combined approach that ...
Added: October 10, 2020
Anwar S., Ustalov D., Arefyev N. et al., , in: Proceedings of the 13th International Workshop on Semantic Evaluation (SemEval-2019).: Minneapolis: Association for Computational Linguistics, 2019. P. 125–129.
We present our system for semantic frame induction that showed the best performance in Subtask B.1 and finished as the runner-up in Subtask A of the SemEval 2019 Task 2 on unsupervised semantic frame induction (Qasem-iZadeh et al., 2019). Our approach separates this task into two independent steps: verb clustering using word and their context ...
Added: October 10, 2020
Arefyev N V., Fedoseev M., Kabanov A. et al., , in: Компьютерная лингвистика и интеллектуальные технологии: по материалам ежегодной международной конференции «Диалог» (Москва, 17–20 июня 2020 г.)Issue 19(26): дополнительный том.: -, 2020. P. 13–32.
Expert-built lexical resources are known to provide information of good quality for the cost of low coverage. This property limits their applicability in modern NLP applications. Building descriptions of lexical-semantic relations manually in sufficient volume requires a huge amount of qualified human labour. However, given some initial version of a taxonomy is already built, automatic ...
Added: October 9, 2020
Struyanskiy O., Arefyev, N., , in: Supplementary Proceedings of the 7th International Conference on Analysis of Images, Social Networks and Texts (AIST-SUP 2018), Moscow, Russia, July 5-7, 2018.: Aachen: CEUR Workshop Proceedings, 2018. P. 208–213.
Attentional neural networks have achieved remarkable results for a number of tasks in the past few years. The fascinating success of neural networks with attention mechanism in natural language processing, especially in machine translation, suggests that these models can capture the meaning of ambiguous words considering their context. In this paper we introduce a new ...
Added: October 9, 2020
Arefyev, N, Boris S., Aleksashina T., , in: Analysis of Images, Social Networks and Texts. 8th International Conference, AIST 2019, Lecture Notes in Computer Science, Revised Selected PapersVol. 11832.: Cham: Springer, 2019. P. 105–121.
Word sense induction (WSI) is the problem of grouping occurrences of an ambiguous word according to the expressed sense of this word. Recently a new approach to this task was proposed, which generates possible substitutes for the ambiguous word in a particular context using neural language models, and then clusters sparse bag-of-words vectors built from ...
Added: October 9, 2020