2024.2

We consider representations of regular languages over symmetric groups such as finite automata and regular expressions. We show that the problem of computing cardinality of such representations is NP-hard.

Polynomiality characterizations are proposed for k-valued logic functions of one variable for a composite modulo k which is a power of a prime number. Based on these characterizations, for each prime number p, polynomiality checking algorithms are obtained for pm-valued logic functions of one variable, m > 1. In these algorithms, the calculations are performed in the residue ring modulo pm. In the case of the positive answer, the algorithms find the canonical polynomial of a input function. The complexity of the obtained algorithms are evaluated (with respect to number of operations from the field of p elements with possible constants).

The paper investigates a two-server system with a Poisson input, in which the service times on the servers have a Pareto distribution with the parameter a > 1. Using known asymptotics for the distribution of stationary waiting time, the distribution of the maximum stationary delay is obtained for two cases: p < 1 and 1 < p < 2. Estimates of the extremal index of stationary waiting time were obtained in numerical experiments using regenerative modeling.

A method of intelligent forecasting of random processes is described. This method is based on a more comprehensive use of statistical regularities inherent in the evolution of the process under consideration. Within the framework of the proposed approach, on the stage of training, the feature space is complemented by the parameters of mixed probability models that make it possible to reconstruct the coefficients of the stochastic differential equation describing the process under consideration. The additional statistical information imposes supplementary restrictions on the research area and thus, narrows the set of possible solutions and directs learning by preliminary rejection of improbable or highly unlikely decisions, and hence, makes the training more efficient and the forecasts more accurate.

The matrix equation XAX = AXA is called the equation of the Young–Baxter type. We examine this equation for matrices of order 2 under the assumption that A is a nonsingular matrix, and we are only interested in the nonsingular solutions. Using a unified rule, one can associate with every such solution a matrix commuting with A. In other words, this matrix is an element of the centralizer MA of A. No obvious reasons exist for two distinct solutions X1 and X2 to generate the same element of MA. Nevertheless, all the solutions (and there are infinitely many of them) generate one and the same matrix in the centralizer. We give an explanation of this surprising fact.

The paper considers an approach to solving the problem of removing noise in a large data set from the sparsity class mp under condition of weak dependence. The approach is based on the method of controlling the false discovery rate (FDR). An upper asymptotic bound for the mean-square risk is obtained.

A method for approximate construction of the boundary of attainability domain is developed for a class of nonsmooth controlled dynamical systems on the plane that arise in economics. The method is based on an explicit procedure for smoothing the system and using the apparatus of the Pontryagin maximum principle. As an example, we consider the problem of constructing the boundary of the attainability domain for a controlled version of the well-known Kaldor’s model of business cycle.