A \(\Pi^0_1\)-bounded fragment of infinitary action logic with exponential

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 ...

Добавлено: 26 декабря 2025 г.

Infinitary action logic with multiplexing

Кузнецов С. Л., Сперанский С. О., 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 ...

Добавлено: 26 декабря 2025 г.

Влияние аксиомы связности на сложность модальной логики.

Кудинов А. В., Мясников К. М., Математика и теоретические компьютерные науки 2025 Т. 3 № 2 С. 58–84

В работе доказывается, что для слабо транзитивных логик с универсальной модальностью, проверку выполнимости формулы для которых можно произвести в PSPACE}, добавление аксиомы связности не увеличивает сложность этой проверки, причем строится явный алгоритм, который решает эту задачу. ...

Добавлено: 14 октября 2025 г.

Are prime numbers and quadratic residues random?

Бланк М. Л., Discrete and Continuous Dynamical Systems 2025 Vol. 45 No. 11 P. 4186–4201

Appeals to randomness in various number-theoretic constructions appear regularly in modern scientific publications. Such famous names as V.I. Arnold, M. Katz, Ya.G. Sinai, and T. Tao are just a few examples. Unfortunately, all of these approaches rely on various, although often very non-trivial and elegant, heuristics. A new analytical approach is proposed to address the ...

Добавлено: 23 мая 2025 г.

Craig's trick and a non-sequential system for the Lambek calculus and its fragments

Кузнецов С. Л., Lugovaya V., Рыжова А. А., Logic Journal of the IGPL 2019 Vol. 27 No. 3 P. 252–266

Добавлено: 1 мая 2025 г.

Syntactic concept lattice models for infinitary action logic

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.

Добавлено: 12 июня 2024 г.

Making first order linear logic a generating grammar

Sergey Slavnov, Logical Methods in Computer Science 2023 Vol. 19 No. 4

Добавлено: 20 декабря 2023 г.

COMPLEXITY OF LAMBEK CALCULI WITH MODALITIES AND OF TOTAL DERIVABILITY IN GRAMMARS

S. M. Dudakov, Karlov B. N., S. L. Kuznetsov и др., Algebra and Logic 2021 Vol. 60 No. 5 P. 308–326

Добавлено: 12 ноября 2023 г.

Modification and Optimization of Pollards's Factorization ρ-Method by Means of Recursive Algorithm of Number Calculation Factorization

Смирнов И. А., Разумов П. В., Болдырихин Н. В. и др., IEEE, 2019.

Добавлено: 10 мая 2023 г.

Реализация ρ–метода факторизации Джона Полларда на языке C++

Черкесова Л. В., Сафарьян О. А., Смирнов И. А., Молодой исследователь Дона 2018 Т. 3 (12) С. 111–121

Представлен проект реализации ρ-метода факторизации Полларда на языке C++, который работает быстрее стандартного алгоритма на 27%. Это помогает значительно облегчить работу в расшифровывании и криптоанализе в различных шифрах, например, таких как RSA. ...

Добавлено: 9 мая 2023 г.

Commutative action logic

Stepan L. Kuznetsov, Journal of Logic and Computation 2023 Vol. 33 No. 6 P. 1437–1462

Добавлено: 7 марта 2023 г.

The complexity of election problems with group-separable preferences

Faliszewski P., Карпов А. В., Obraztsova S., Autonomous Agents and Multi-Agent Systems 2022 Vol. 36 Article 18

Добавлено: 14 марта 2022 г.

Decidable Fragments of Calculi Used in CatLog

Канович М. И., Kuznetsov Stepan G., Кузнецов С. Л. и др., Studies in Computational Intelligence 2021 Vol. 999 P. 1–24

Добавлено: 14 декабря 2021 г.

Language models for some extensions of the Lambek calculus

Канович М. И., Кузнецов С. Л., Щедров А., Information and Computation 2022 Vol. 287 Article 104760

Добавлено: 4 декабря 2021 г.

On embedding Lambek calculus into commutative categorial grammars

Славнов С. А., Journal of Logic and Computation 2022 Vol. 32 No. 3 P. 479–517

Добавлено: 21 октября 2021 г.

The multiplicative-additive Lambek calculus with subexponential and bracket modalities

Канович М. И., Кузнецов С. Л., Щедров А., Journal of Logic, Language and Information 2021 Vol. 30 No. 1 P. 31–88

Добавлено: 25 ноября 2020 г.

Reconciling Lambek's restriction, cut-elimination, and substitution in the presence of exponential modalities

Канович М. И., Кузнецов С. Л., Щедров А., Journal of Logic and Computation 2020 Vol. 30 No. 1 P. 239–256

Добавлено: 1 июля 2020 г.

The complexity of multiplicative-additive Lambek calculus: 25 years later

Канович М. И., Кузнецов С. Л., Щедров А., , in: Logic, Language, Information, and Computation: 26th International Workshop, WoLLIC 2019, Utrecht, The Netherlands, July 2-5, 2019, ProceedingsVol. 11541: Lecture Notes in Computer Science.: Berlin, Heidelberg: Springer, 2019. P. 356–372.

Добавлено: 4 сентября 2019 г.

L-models and R-models for Lambek calculus enriched with additives and the multiplicative unit

Добавлено: 4 сентября 2019 г.

A Logical Framework with Commutative and Non-commutative Subexponentials

Канович М. И., Кузнецов С. Л., Nigam V. и др., , in: 9TH INTERNATIONAL JOINT CONFERENCE ON AUTOMATED REASONINGIssue 10900.: Springer International Publishing AG, part of Springer Nature 2018, 2018. P. 228–245.

Добавлено: 11 июля 2018 г.

The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions

Шитов Я. Н., SIAM Review 2017 Vol. 59 No. 4 P. 794–800

Добавлено: 9 ноября 2017 г.

Horn fragments of the Halpern-Shoham interval temporal logic

Захарьящев М. В., BRESOLIN D., KURUCZ A. и др., , in: ACM Transactions on Computational Logic (TOCL)Vol. 18. Issue 3.: NY: ACM, 2017. P. 1–39.

We investigate the satisfiability problem for Horn fragments of the Halpern-Shoham interval temporal logic depending on the type (box or diamond) of the interval modal operators, the type of the underlying linear order (discrete or dense), and the type of semantics for the interval relations (reflexive or irreflexive). For example, we show that satisfiability of ...

Добавлено: 17 сентября 2017 г.