?
О задачах регулярной реализуемости для контекстно-свободных языков
Проблемы передачи информации. 2015. Т. 51. № 4. С. 47–59.
Vyalyi M., Rubtsov A. A.
We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.
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
Alexander Rubtsov, Chudinov N., , in: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024).: Leibniz International Proceedings in Informatics (LIPIcs), 2024. Ch. 80 P. 80:1–80:13.
We present a computational model for Parsing Expression Grammars (PEGs). The predecessor of PEGs top-down parsing languages (TDPLs) were discovered by A. Birman and J. Ullman in the 1960-s, B. Ford showed in 2004 that both formalisms recognize the same class named Parsing Expression Languages (PELs). A. Birman and J. Ullman established such important properties ...
Added: November 24, 2024
Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2024 Vol. 18 P. 1273–1283
For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or max min ) path problem is to find the maximum value of path-minimum edge capacities among all paths, connecting s and t. It can be generalized by finding the bottleneck values between s and all possible t. These problems arise ...
Added: April 18, 2024
Semenov A., В кн.: Всемирный конгресс (26–30 июня 2023 г., Москва). Теория систем, алгебраическая биология, искусственный интеллект: математические основы и приложения: Избранные труды.: М.: [б.и.], 2023. С. 390–405.
Added: March 13, 2024
Malyshev D., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801
For a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any adjacent edges receive different colors. For all classes defined by sets of forbidden subgraphs, each with 7 edges, the complexity status of this problem is known. In this paper, we obtain ...
Added: February 16, 2024
Gerasimova O., Makarov I., Severin N., IEEE Access 2023 Vol. 11 P. 88074–88086
The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings ...
Added: January 5, 2024
Мещеряков М. В., Сухарев Л. А., Саранск: Изд-во Мордовского университета, 2018.
The book is an introductory course on the theory of formal languages and finite automata. It presents the main material of diciplina related to the mathematical foundations of a number of syntactic methods of inormatics and programming. The book is intended for undergraduate students in the following fields of study: fundamental computer science and information ...
Added: October 12, 2023
Sergei Valentinovich Fedorenko, IEEE Access 2023 Vol. 11 P. 62771–62779
The novel methods for binary discrete Fourier transform (DFT) computation over the finite field have been proposed. The methods are based on a binary trace calculation over the finite field and use the cyclotomic DFT. The direct DFT computational complexity has been reduced due to using the binary trace function over the finite field and ...
Added: July 19, 2023
Complexity function and complexity of validity of modal and superintuitionistic propositional logics
Rybakov M., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566–1595
We consider the relationship between the algorithmic properties of the validity problem for a modal or superintuitionistic propositional logic and the size of the smallest Kripke countermodels for non-theorems of the logic. We establish the existence, for every degree of unsolvability, of a propositional logic whose validity problem belongs to the degree and whose every ...
Added: January 6, 2023