?
On computational complexity of set automata
Information and Computation. 2021. Vol. 281. Article 104797.
Rubtsov A. A., Vyalyi M.
We consider a computational model which is known as set automata. The set automata are one-way finite automata with additional storage-the set. There are two kinds of set automata-deterministic (DSA's) and nondeterministic (NSA's). The model was introduced by Kutrib, Malcher, Wendlandt in 2014. It was shown that DSA-recognizable languages look similar to DCFL's and NSA-recognizable languages look similar to CFL's.
In this paper, we extend this similarity and prove that languages recognizable by NSA's form a rational cone, as do CFL's.
The main topic of this paper is computational complexity: we prove that
languages recognizable by DSA's belong to P and there are P-complete languages among them;
languages recognizable by NSA's are in NP and there are NP-complete languages among them;
the word membership problem is P-complete for DSA's without epsilon-loops and PSPACE-complete for general DSA's;
the emptiness problem is PSPACE-complete for DSA's.
Keywords: Computational Complexityrational coneFormal LanguageSet automatonmembership problememptiness problem
Publication based on the results of:
Фирсанова В. И., ACM, 2026.
The inclusion of autistic people can be augmented by a mobile app that provides information without a human mediator making information perception more liberating for people in the spectrum. This paper is an overview of a doctoral work dedicated to the development of a web-based mobile tool for supporting the inclusion of people on the ...
Added: August 4, 2026
Фирсанова В. И., Хлусова Я. К., CEUR Workshop Proceedings, 2025.
Knowledge graphs are widely used in Retrieval Augmented Generation (RAG) and Explainable AI (XAI), since they can illustrate semantic relationships generated by Large Language Models (LLMs). Recent studies focus on generating knowledge graphs from unstructured data to improve RAG performance; however, they do not explain the underlying graph structure. The analysis of synthetic graphs behind ...
Added: August 4, 2026
Belomestny D., Gasnikov A., Gladin E. et al., Russian Mathematical Surveys 2026 Vol. 81 No. 4(490) P. 3–90
Reinforcement learning (RL) is increasingly grounded in tools from probability, optimization, and operator theory. This survey organizes the mathematical structures that underpin the design and analysis of modern algorithms in RL. We begin from Markov decision processes (MDPs) and the Bellman operators, emphasizing contraction mappings, monotonicity, and fixed-point theory that yield convergence guarantees and rates ...
Added: August 3, 2026
Chepovskiy A., Мастерская Печати Идей, 2026.
The textbook presents methods and algoгithms for automatic analysis
of соrроrа of texts in natural languages. It is intended fоr sfudenБ of
methods of processing texts in паtчrаl languages and creating training
arays of texts.
Fоr students, graduate students and researchers studying methods
of computational linguistics and word processing. ...
Added: August 1, 2026
Ponomarenko A., / Series Computer Science "arxiv.org". 2025.
This paper addresses the challenge of merging hierarchical navigable small world (HNSW) graphs, a critical operation for distributed systems, incremental indexing, and database compaction. We propose three algorithms for this task: Naive Graph Merge (NGM), Intra Graph Traversal Merge (IGTM), and Cross Graph Traversal Merge (CGTM). These algorithms differ in their approach to vertex selection ...
Added: July 30, 2026
Уилкокс П., Romanov A., М.: ДМК Пресс, 2025.
Книга, которую вы держите в руках, продолжает серию «Книжная полка истового
инженера», которая издается при поддержке компании YADRO.
Данная книга представляет собой учебник по теоретическим основам продвинутой
функциональной верификации и содержит лучшие практики, используемые в настоящее
время. В ней подробно описана унифицированная методология верификации
(UVM) и раскрыты такие темы, как функциональный виртуальный прототип, функциональное
покрытие, утверждения, формальная верификация, тестбенчи, косимуляция,
эмуляция, аппаратное ...
Added: July 30, 2026
Mikhaylets E. V., Razorenova A. М., Chernyshev V. L. et al., Scientific Reports 2026 Vol. 16 Article 23560
Meditation offers a naturalistic paradigm for studying introspection, yet the neural dynamics of advanced tantric practices remain largely unexplored. Buddhist Highest Yoga Tantra (BHYT) comprises a sequence of eight dissolution stages culminating in the “clear light” state. We recorded EEG during eyes-closed BHYT meditation performed in monasteries and hermitages (51 sessions from 36 male practitioners; ...
Added: July 29, 2026
Думкин Н. А., Alexandrov D., Прозорский М. А., Труды Института системного программирования РАН 2026 Т. 38 № 1 С. 255–274
A theoretically sound approach to adaptive client-side video fragment restoration is proposed using
machine learning and scene analysis methods. The method includes a formal problem statement, a finite-state
machine model for decision making, a restoration cost function, and a new stage in video preparation: scene
dynamics assessment followed by recording a feature in an HLS playlist. This feature ...
Added: July 27, 2026
Cham: Springer, 2026.
This open access set, LNAI 16688-16689, constitutes the proceedings of the 13th International Joint Conference, IJCAR 2026, held in Lisbon, Portugal, during July 26–29, 2026.
The 41 full research papers and 8 short papers included in these two volumes were carefully reviewed and selected from 112 submissions. The papers cover the following topical sections:
Part I: Theorem ...
Added: July 26, 2026
Edward R. Rzaev, Aleksandr Y. Romanov, Andrey M. Sukhov, IEEE Access 2026 Vol. 14 P. 2169–3536
This work presents a hierarchy of strictly local fault-tolerant routing algorithms for 3D mesh networks-on-chip, culminating in an algorithm that combines a live-neighbor selection rule with a bounded single-hop rollback mechanism. The proposed algorithms operate exclusively on immediate neighbor information, maintain O(1) per hop complexity, and require no global topology knowledge, additional virtual channels, or ...
Added: July 23, 2026
Pislyakov V., Вестник Томского государственного университета. Филология 2026 № 101 С. 175–192
This article examines the use of proverbs in academic texts—specifically, articles published in Russian research journals. For the experiment, ten proverbs were selected as the intersection of two fundamentally different paremiological surveys aimed at compiling lists of popular or common Russian proverbs. One of these surveys was conducted by the classic of paremiology, G.L. Permyakov, ...
Added: July 22, 2026
Association for Computing Machinery (ACM), 2026.
Wominjeka, and welcome to the 49th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2026), held in Melbourne | Naarm, Australia, from 20–24 July 2026. SIGIR 2026 takes place on the unceded lands of the Woi Wurrung and Boon Wurrung language groups of the eastern Kulin nation, and we pay our ...
Added: July 22, 2026
Korogod D., Shapeev A., Ivan S. Novikov, Physical Review B: Condensed Matter and Materials Physics 2026 Vol. 114 No. 2 Article 024104
We present two models with explicit long-range electrostatics in the form of Coulomb interactions. Both models include point charges depending on their local atomic environments, and the second model also conserves a total charge of an atomic system. We combine the proposed long-range models with the local moment tensor potential (MTP) and demonstrate that they ...
Added: July 22, 2026
Sozykin K., Rybin N., Chertkov A. et al., Physical Review B: Condensed Matter and Materials Physics 2026 Vol. 113 No. 22 Article 224111
The global optimization of atomic clusters represents a fundamental challenge in computational chemistry and materials science due to the exponential growth of local minima with system size (i.e., the curse of dimensionality). We introduce a framework that overcomes this limitation by exploiting the low-rank structure of potential energy surfaces through tensor train (TT) decomposition. Our ...
Added: July 22, 2026
Михайлов И. А., Machine Learning and Knowledge Extraction 2026 Vol. 8 No. 1 Article 8
Whole-slide histology images (WSIs) can exceed 100 k × 100 k pixels, making direct pixel-level segmentation infeasible and requiring patch-level classification as a practical alternative for downstream WSI segmentation. However, most approaches either treat patches independently, ignoring spatial and biological context, or rely on deep graph models prone to oversmoothing and loss of local tissue ...
Added: July 16, 2026
Kuninets A., Malygina E., Leevik A. G. et al., Journal of Computer Virology and Hacking Techniques 2026 No. 22 Article 62
In this work, we investigate the application of Barnes–Wall lattices in post-quantum cryptographic schemes. We survey and analyze several constructions of Barnes–Wall lattices, including subgroup chains, the generalized k-ing construction, and connections with Reed-Muller codes, highlighting their equivalence over both Z[i] and Z. Building on these structural insights, we introduce a new algorithm for efficient ...
Added: July 16, 2026
Silakov D., Системный администратор 2026 № 5 С. 46–51
В предыдущей статье про Open Source в КНР [1] мы рассказали про Alibaba – крупную корпорацию, занимающую тридцатое место в рейтинге самых значимых мировых брэндов за 2025 год [2]. Место почетное, но не первое среди китайских компаний – на тринадцатом месте расположилась Tencent, разработчик WeChat и ряда других продуктов, широко используемых нашими восточными соседями. Tencent ...
Added: July 14, 2026
IEEE, 2026.
Added: July 13, 2026
Switzerland: Springer, 2026.
This volume contains the refereed proceedings of the 25th International Conference on Mathematical Optimization Theory and Operations Research (MOTOR 2026) 1 held during July 6–11 in a picturesque place near Lake Baikal, Irkutsk, Russia. The MOTOR conference is a direct successor and scientific inheritor of several prominent events on mathematical programming, combinatorial and stochastic optimization, ...
Added: July 12, 2026
Шиманогов И. Н., Vyalyi M., Дискретный анализ и исследование операций 2025 Т. 32 № 4(166) С. 213–230
A well-studied class of algorithmic problems is that of regular realizability: checking the non-emptiness of the intersection of a regular language with a given language. This problem has a natural algebraic interpretation: verifying whether an element of a Boolean algebra belongs to the kernel of a certain homomorphism. This motivates the consideration of an analogous ...
Added: July 12, 2026
Surkov A., Ignatenko V., Koltsov S., Computers, Materials and Continua 2026 Vol. 88 No. 3 Article 74
Large language models have recently demonstrated promising capabilities in mathematical reasoning; however, their performance on tasks requiring strict symbolic manipulation, such as solving differential equations, remains limited, especially for compact models. In this work, we investigate whether activation steering combined with reinforcement learning can improve the quality of solutions generated by pretrained language models without ...
Added: July 8, 2026
Springer, 2027.
The series Lecture Notes in Computer Science (LNCS), including its subseries Lecture Notes in Artificial Intelligence (LNAI) and Lecture Notes in Bioinformatics (LNBI), has established itself as a medium for the publication of new developments in computer science and information technology research, teaching, and education. LNCS enjoys close cooperation with the computer science R & ...
Added: July 8, 2026
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
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