?
Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино?
Логические исследования. 2023. Т. 29. № 1. С. 114–146.
Tiling problems are a convenient tool for studying algorithmic complexity of problems arising in various branches of mathematics, including logic. The paper describes modelling of domino problems using the first-order language, as well as some additional language constructs, some of which are not elementary. This enables us both to obtain simple proofs of known facts about undecidability of satisfiability problems for various fragments of the first-order language and to obtain some new results. It is known that the satisfiability problem for the first-order formulas containing at most two individual variables is decidable; it is also known that the transitivity of a binary relation and the composition of binary relations are first-order definable with formulas of three individual variables. We show that addition of the operator of transitivity test for a binary relation (or a stronger tool, the transitive closure operator), together with the operator of composition, results in an undecidable satisfiability problem for formulas with two individual variables, a single binary predicate letter, and equality.
Tyukin I., Tyukina T., van Helden D. P. et al., Information Sciences 2024 Vol. 678 Article 120856
AI errors pose a significant challenge, hindering real-world applications. This work introduces a novel approach to cope with AI errors using weakly supervised error correctors that guarantee a specific level of error reduction. Our correctors have low computational cost and can be used to decide whether to abstain from making an unsafe classification. We provide ...
Added: May 23, 2026
Zaikin A., Sviridov I., Sosedka A. et al., Technologies 2026 Vol. 14 No. 2 Article 84
High-dimensional tabular data are common in biomedical and clinical research, yet conventional machine learning methods often struggle in such settings due to data scarcity, feature redundancy, and limited generalization. In this study, we systematically evaluate Synolitic Graph Neural Networks (SGNNs), a framework that transforms high-dimensional samples into sample-specific graphs by training ensembles of low-dimensional pairwise ...
Added: May 23, 2026
Kibkalo Vladislav, Chertopolokhov V., Mukhamedov A. et al., IEEE Access 2026 Vol. 14 P. 14369–14392
This study presents on-the-fly identification and multi-step prediction of nonlinear systems with delayed inputs using a dynamic neural network combined with a smooth projection onto ellipsoids. The projection enforces parameter constraints that guarantee stability, while a Lyapunov–Krasovskii analysis yields computable ultimate error bounds. Riccati-type matrix inequalities are derived, providing an efficient vectorization–projection–devectorization implementation suitable for ...
Added: May 22, 2026
Морозов С. В., Calcolo 2026 Vol. 63 No. 2 Article 23
The approximation of tensors in a low-para metric format is a crucial component in many mathematical modelling and data analysis tasks. Among the widely used low-parametric representations, the canonical polyadic (CP) decomposition is known to be very efficient. Nowadays, most algorithms for CP approximation aim to construct the approximation in the Frobenius norm; however, some ...
Added: May 22, 2026
Селянин Ф. И., Journal of Dynamical and Control Systems 2026 Vol. 32 No. 2 P. 1–16
A B-facet is a lattice -dimensional polytope in the positive octant with a positive normal covector, such that every -dimensional simplex with vertices in it is a B-simplex (i.e., a pyramid of height one with base on a coordinate hyperplane). B-facets were introduced in [2] in the context of the monodromy conjecture. In this paper, we complete the ...
Added: May 21, 2026
Ausubel L., Baranov O., Journal of Economic Theory 2026 Vol. 235 No. 106192
The Vickrey-Clarke-Groves (VCG) mechanism is one of the most compelling constructs in mechanism design, but the presence of complementary goods creates the possibility of non-core and even zero-revenue outcomes. In this article, we show that joint feasibility constraints on allocations offer a second pathway to ill-behaved outcomes in the VCG mechanism, even when all bidders ...
Added: May 20, 2026
Denis Seliutskii, Russian Journal of Mathematical Physics 2025 Vol. 32 No. 2 P. 399–407
In this paper, we find an upper bound for the first Steklov eigenvalue for a surface of revolution with boundary consisting of two spheres of different radii. Moreover, we prove that, in some cases, this boundary is sharp. ...
Added: May 19, 2026
Жакупов О. Б., European Journal of Mathematics 2025 Vol. 11 Article 84
We provide examples of smooth three-dimensional Fano complete intersections of degree 2, 4, 6, and 8 that have absolute coregularity 0. Considering the main theorem of Avilov, Loginov, and Przyjalkowski (CNTP 18:506–577, 2024) on the remaining 101 families of smooth Fano threefolds, our result implies that each family of smooth Fano threefolds has an element of absolute ...
Added: May 18, 2026
Gonchenko S., Lerman L., Turaev D., Regular and Chaotic Dynamics 2026 Vol. 31 No. 3 P. 349–369
We show that bifurcations of four-dimensional symplectic diffeomorphisms with a quadratic homoclinic tangency to a saddle periodic orbit with real multipliers produce 2-elliptic periodic orbits if the tangency is not partially hyperbolic. We show that a normal form for the rescaled first-return maps near such tangency is given by a four-dimensional symplectic H´enonlike map and study bifurcations of the ...
Added: May 15, 2026
Aleskerov F. T., Khutorskaya O., Stepochkina A. et al., Springer, 2026.
The book contains new models of bibliometric analysis based on centrality measures in network analysis, pattern analysis and stability analysis. A distinctive feature of these centrality measures is that they account for the parameters of vertices and group influence of vertices to a vertex. This reveals specific groups of publications, authors, terms, journals and affiliations ...
Added: May 15, 2026
Kuptsov P., Panyushev A., Stankevich N., Chaos 2026 Vol. 36 No. 5 Article 053138
We develop a machine-learning approach to reproduce the behavior of two versions of the van der Pol oscillator exhibiting a subcritical Andronov–Hopf bifurcation, with or without a codimension-2 Bautin point. We construct a neural-network model that functions as a recur rent map and train it on short segments of oscillator trajectories. The results show that, ...
Added: May 15, 2026
Dorovskiy A., / Series arXiv "math". 2026.
In this paper the structural stability of generic families of vector fields of the PC-HC class on the two-dimensional sphere is proved. A classification of these families up to moderate equivalence in neighborhoods of their large bifurcation supports is presented, based on such invariants as the configuration and the characteristic set. The realization lemma is proved. ...
Added: May 14, 2026
Lebedev V., Journal of Mathematical Analysis and Applications 2026 Vol. 563 No. 2 Article 130787
It is known that for every continuous real-valued
function $f$ on the circle $\mathbb T=\mathbb R/2\pi\mathbb Z$ there exists a
change of variable, i.e., a self-homeomorphism $h$ of $\mathbb T$, such that
the superposition $f\circ h$ is in the Sobolev space $W_2^{1/2}(\mathbb T)$.
We obtain new results on simultaneous improvement of functions by a single
change of variable in relation ...
Added: May 14, 2026
Blokh A., Oversteegen L., Selinger N. et al., Arnold Mathematical Journal 2026 Vol. 12 No. 1 P. 60–110
We describe a model for the boundary of the connectedness locus of the parameter space of cubic symmetric polynomials. We show that there exists a monotone continuous function from the connectedness locus to the model which is a homeomorphism if the former is locally connected. ...
Added: May 13, 2026
Petrov I., Автоматика и телемеханика 2026 № 6 С. 82–118
Системам связанных агентов и сетевому управлению посвящено большое число отечественных и зарубежных исследований. Исторически, наибольший интерес в теории управления возникал к усредняющим системам и, в частности, к задаче консенсуса. Однако сетевое взаимодействие может характеризоваться более специфическими функциями, отражающими зависимость от действий соседей по сети, что особенно явно проявляется в моделях стратегического взаимодействия на сети, которое ...
Added: May 12, 2026
М.: ООО «Макс Пресс», 2026.
В настоящем сборнике представлены тезисы докладов участников семинара "Интеграция основного и дополнительного физико-математического образования", проходившего 11 февраля 2026 года в ГБОУ Школа №2007 ФМШ г. москвы, а также другие публикации, посвящённые вопросам дополнительного физико-математического образования. ...
Added: May 11, 2026
Dudakov S., Математика и теоретические компьютерные науки 2024 Т. 2 № 4 С. 51–65
We study the additive theory of arbitrary figures in linear spaces, that is, the theory of addition extended to sets of vectors. Our main result is the following: if a linear space is infinite, then the additive theory of figures allows to interpret second-order arithmetic and, therefore, has this or higher degree of undecidability. For ...
Added: March 18, 2026
Dudakov S., Вестник Тверского государственного университета. Серия: Прикладная математика 2025 № 1 С. 5–13
For infinite linear spaces, in our previous works, we have shown that theories of figures and subspaces are of high undecidability degree. They allow interpreting elementary arithmetic or second-order arithmetic (for infinite figures). For finite linear spaces, such a claim doesn't hold. It is because we can algorithmically enumerate all finite linear spaces and find ...
Added: March 18, 2026
Dudakov S., Известия РАН. Серия математическая 2025 Т. 89 № 2 С. 3–24
We consider algebras of finite subsets under the assumption that the original algebra is an infinite groupoid. For linear spaces over fields of finite characteristic, we prove that the finite subsets algebra is algorithmically equivalent to the first-order arithmetic. We also generalize this result to arbitrary infinite Abelian groups. As a corollary, for many classes ...
Added: March 18, 2026
Rybakov M., Вестник Тверского государственного университета. Серия: Прикладная математика 2023 № 1 С. 5–23
Доказывается неразрешимость и сильная неразрешимость (неарифметичность) теорий классов деревьев (при различных уточнениях понятия дерева и при различных требованиях к свойствам деревьев, включая конечность числа вершин) в языке с бинарной предикатной буквой, соответствующей дугам, равенством, оператором транзитивного замыкания и конгруэнтностью между парами вершин, которая определяется как равенство расстояния между вершинами первой пары расстоянию между вершинами второй ...
Added: July 7, 2023
The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups
Birget J., Talambutsa A., International Journal of Algebra and Computation 2022 Vol. 32 No. 6 P. 1261–1274
In this paper, we define the symmetric Post Correspondence Problem (PCP) and prove that it is undecidable. As an application, we show that the original proof of undecidability of the freeness problem for 3×3 integer matrix semigroups works for the symmetric PCP, but not for the PCP in general. ...
Added: December 9, 2022
Poddiakov A., В кн.: Когнитивная психология.: М., Саратов: ПЕР СЭ, Ай Пи Эр Медиа, 2024. С. 202–204.
Рассматривается значение алгоритмической неразрешимости для когнитивной психологии. ...
Added: October 29, 2021
Zolin E., В кн.: Одиннадцатые Смирновские чтения по логике: материалы Международной научной конференции, 19 – 21 июня 2019, г. Москва.: М.: Современные тетради, 2019. С. 24–26.
В модальной теории соответствия [1, Sect. 3.5] говорят, что формула
первого порядка с одной свободной переменной 𝑞(𝑥) сигнатуры {𝑅,=}, где
𝑅 – бинарный предикатный символ, соответствует модальной формуле 𝐴, если для любой шкалы Крипке 𝐹 = (𝑊,𝑅) и точки 𝑤 ∈ 𝑊, имеем: 𝐹 |= 𝑞(𝑤) ⇔ 𝐹,𝑤 |= 𝐴. Будем обозначать соответствие 𝑞(𝑥)!𝐴, следуя [4], где ...
Added: June 30, 2019
Nabebin A. A., М.: Научный мир, 2010.
Излагаются основные понятия дискретной математики: модулярная арифметика и ее использование в криптографии, элементы комбинаторики, алгебра логики и логика предикатов, теория графов, конечные автоматы. ...
Added: May 28, 2012