SovietRxiv · Open Access in English
Rediscovering the Soviet scientific archive, in English
25357 full-text translations 14926 English PDFs 22539 abstracts
Showing 50 of 482 papers
This paper studies the complexity of normal algorithms associated with realizability for closed logico-arithmetical formulas of bounded length and with bounded realizations of certain propositional formulas under arithmetical substitution. It defines complexity as the length of an algorithm’s repres…
This note studies generative grammars under bounds on the number of auxiliary symbols that may occur during derivations, called active capacity, distinguishing bounded and uniformly bounded variants. It reduces the analysis to context-sensitive grammars, introduces a density measure for derivation t…
This paper studies whether algorithmically unsolvable mass problems can nevertheless be solved correctly on almost all instances along infinitely many initial segments. For recursively enumerable sets, it proves that for every positive error bound there is a general recursive predicate agreeing with…
This paper derives an analytical attitude control law for a spatial rotational maneuver of a flying vehicle, formulated as a single rotation about a prescribed axis rather than as three successive body-axis rotations. Using Euler equations, inertia transformations, and the principle of extensive con…
This note interprets Tikhonov regularization for ill-posed statistical optimization problems in control systems from an information-theoretic viewpoint. For a Gaussian signal corrupted by additive Gaussian noise, the authors formulate a regularized mean-square filtering problem and show that the res…
This paper studies zero-sum differential games of fixed duration in which one player observes the current state while the minimizing player receives state information only after a fixed lag. A discrete-time approximation is introduced to define information sets, pure, mixed, and behavioral strategie…
The paper studies two problems in graph theory: finding minimum weight Hamiltonian circuits in directed and undirected graphs with integer edge or arc weights, and finding minimum edge coverings of graphs. It proposes a simple quadratic time algorithm that first constructs a long path and then inser…
The paper addresses the problem of constructing the transitive closure of a directed graph more economically than the standard cubic bound, focusing on the acyclic case as a component of a broader reduction for general graphs. It partitions the vertices of an acyclic graph into ranks and expresses t…
The paper addresses the observation problem for nonlinear dynamical systems, specifically the determination of unmeasured phase coordinates or initial state values from measured output signals. It proposes embedding the nonlinear system in a parameter-dependent family whose zero-parameter member is …
This paper introduces and studies auto-reducibility for mass problems, formalized as membership problems for sets of natural numbers, using oracle machines that compute each value without querying that value itself. It relates non-auto-reducibility to Kolmogorov and Loveland selection-based randomne…
The paper studies observability for linear controlled systems when the observer knows the dynamics and the measured output but not the applied control. It defines ideal observability as unique reconstruction of the initial state from the output for all admissible controls, relates this notion to Kal…
This note estimates how many errors are corrected by Reed decoding of binary Reed-Muller codes beyond the usual guaranteed minimum-distance bound. Using combinatorial estimates for the parity distribution of errors across coordinate groups, Fourier coefficient representations, and asymptotic probabi…
This paper studies feedback control laws that maximize the domain of asymptotic stability for systems whose uncontrolled plant may be unstable. It defines stability optimality as inclusion maximality of the attraction domain and proves, under broad admissibility assumptions, the existence of an admi…
This paper studies the dynamics of a simple nonlinear impulse control system containing an integrating element, a static nonlinearity, and a linear distributed element governed by a parabolic boundary-value problem. Using point transformations at impulse instants, it derives finite-iteration mapping…
The paper addresses one-to-one coding of words and statements over arbitrary finite alphabets, in contrast to contraction methods that may lose uniqueness and prevent recovery of the original text. It defines alphabets, dictionaries, words, and statements formally, then constructs a coding by identi…
This paper studies linearized perturbed motion in nonstationary automatic control systems whose plant and regulator parameters vary slowly and whose regulator action is represented by convolution integrals with impulse transient functions. It develops a formal asymptotic construction for particular …
This paper proposes a Monte Carlo algorithm for estimating the eigenvalue of largest modulus of an integral operator by iterating the resolvent rather than the operator itself. The method represents powers of the resolvent through a binomial operator expansion and expresses the required scalar produ…
The paper studies completeness of systems of functions in finite-valued logic under codings of finite sets and up to coding, with emphasis on the three-valued case. It introduces a partial order on equivalence classes of codings by majorization, analyzes special codings, and uses these notions to re…
This paper strengthens earlier results on evasion in linear differential games governed by a system with compact convex control sets for the pursuer and evader, where termination occurs when the phase vector reaches a fixed subspace. It proves an evasion theorem for the case in which the orthogonal …
This note studies quantitative characteristics of algorithmic languages, focusing on how briefly algorithms can be encoded and compared through translators between languages. It defines reducibility, message complexity, additive, asymptotic, and multiplicative boundedness of translators, and corresp…
This note formulates a general scheme for a method used in several classes of discrete optimization problems, including production allocation, integer linear programming, discrete programming, concave programming, and reliability problems. The problem is to minimize a function on a finite feasible s…
This paper gives elementary constructions of universal functions for partial recursive functions using a polynomial pairing-like map on natural numbers. It proves that any partial binary arithmetical operation satisfying three simple identities relative to this polynomial is recursively complete, an…
This paper studies the state complexity of operations on regular sets of words represented by finite automata, taking the number of states in a minimal representing automaton as the complexity measure. It gives binary alphabet examples showing that known upper bounds for union, product, and iteratio…
This note applies Strassen’s fast matrix multiplication to the computation of the transitive closure of a directed graph. It observes that Boolean matrix multiplication can be carried out by ordinary multiplication of zero one matrices followed by thresholding, giving a bound of order n to the log b…
This paper studies absolute stochastic stability for automatic control systems represented by nonlinear Volterra integral equations with random external inputs. It defines stochastic stability in terms of functionals measuring the input process and the corresponding solution, and derives frequency-d…
This paper studies lower bounds on the complexity, defined as representation length, of normal algorithms that decide or enumerate predicates on finite sets of words. It introduces a reducibility notion for normal algorithms and proves that universality with respect to this reducibility is equivalen…
The note studies space complexity analogues of known undecidability results for algorithmic problems in finitely presented groups and semigroups, especially word, conjugacy, and individual conjugacy problems. By refining constructions of Bokut, Collins, and Shepherdson and estimating the associated …
This paper compares several restricted classes of predicates used in algorithm theory, including rudimentary, bounded-arithmetical, logarithmic Turing-computable, real-time, marked-machine, context-free, and s-rudimentary predicates. Its main tool is a sufficient condition showing that predicates co…
The paper studies the decoding of finite Mealy automata treated as black boxes when no upper bound on the number of states is available, focusing on what can be achieved by simple experiments rather than multiple branching experiments. It formalizes decoding algorithms, introduces a uniform frequenc…
The paper studies an algebraic representation problem arising in control theory for a controllable linear system with a Hermitian form in the state and input variables. It seeks conditions under which the form can be written as the derivative of a quadratic Lyapunov-type expression plus a quadratic …
This paper studies qualitative stability and instability in the large for a class of discrete amplitude-pulse automatic control systems consisting of a linear difference equation coupled to nonlinear modulators with memory. Using quadratic forms, transfer-function conditions on the unit circle, and …
The paper develops a method for determining limiting characteristics and capacities of linear information systems with feedback and internal interference, such as reproduction or tracking systems. Assuming stationary Gaussian input signal, external noise, and internal disturbance with known spectral…
This paper examines variable-structure automatic control systems in which the control law uses internal system coordinates, a technique that can avoid repeated differentiation of the error signal but may make the sliding hyperplane and transient dynamics sensitive to plant parameter variations. The …
This paper develops necessary optimality conditions for control systems with aftereffect, where the dynamics are defined by functionals depending on past state and control histories. Using an auxiliary adjoint function and a functional analogue of the Hamiltonian, it derives an increment formula for…
This paper studies random binary tables and the asymptotic behavior of dead-end tests, understood as minimal sets of columns that distinguish all rows. It derives estimates for the probability that a selected set of columns is a dead-end test and uses them to obtain asymptotic formulas for the expec…
The paper addresses the construction of coding systems for channels with asymmetric distortions, including errors modeled by nonnegative modular noise, and relates this problem to an additive combinatorial problem on distinct nonzero sums modulo an integer. It develops algebraic identities for symme…
The paper studies how imposing bounds on running time affects the representation complexity of normal algorithms. It formulates estimates for algorithms deciding applicability to words of bounded length, for algorithms recognizing M-noncomputability of Boolean functions, and for algorithms minimizin…
This paper studies the complexity of normal algorithms that decide, on all words up to a given length, whether another algorithm is applicable. It defines lower and upper estimates for such resolving algorithms and proves that, for any nondecreasing general recursive function bounded by the identity…
The paper proposes a macromodel for evaluating the efficiency of large information control systems consisting of a controlled object and a controlling subsystem linked by a flow of control information. It defines efficiency as the difference between the positive effect released in the object and the…
The paper studies finitely convergent iterative algorithms for solving countable systems of inequalities that arise in the synthesis of adaptive control systems, where the inequalities are revealed sequentially and may contain unknown quantities. It develops several correction algorithms for quadrat…
This paper studies whether exhaustive search can be avoided when computing a function using an oracle for its own graph, where computation proceeds by questions of the form “is the value at this argument equal to this number?” It formalizes guessing strategies by Turing machines with such oracles, d…
The paper presents iterative methods for sectoral planning problems formulated as integer linear programs with binary variables and assignment-type restrictions. It first describes a primal-dual iterative procedure for the corresponding continuous linear programming relaxation, using adaptive price …
This paper studies functional equivalence for finite control automata with a final state in Glushkov’s framework of interacting control and operational automata. It defines operators and conditions syntactically over variables, function symbols, and predicate symbols, interprets automata over arbitr…
This paper studies complexity bounds for normal algorithms and for deciding enumerable sets when computation time is restricted. It first proves a coding theorem showing that algorithms constructively generated from words over one alphabet can be represented over a two-letter extension of another al…
The paper studies upper bounds for the formula size, measured by number of letters, required to realize monotone symmetric Boolean threshold functions in the basis of disjunction, conjunction, and negation. It develops an indirect counting argument over specially structured formula trees, choosing b…
The paper studies optimal questionnaires for identifying one event from a finite weighted set when questions may have different arities and unequal costs. It models a questionnaire as a rooted tree or pragraph, defines the expected traversal cost as the weighted sum of path costs, and analyzes trans…
This paper studies decoding automata for memoryless encodings that can self-adjust after input substitution errors, certain state failures, and, in a generalized finite case, shifts of the input sequence. It introduces semibounded and \((l,m)\)-semibounded automata, characterizes them through comple…
This note studies the asymptotic correcting capabilities of random binary linear codes of length n and dimension k equal to the integer part of nR, with fixed rate 0 < R < 1. Using a uniform probability measure on generator matrices, it analyzes the distribution of the minimum nonzero codeword weigh…
This note studies the problem of recognizing the final state of a finite automaton treated as a black box, with particular attention to the length of the shortest homogeneous experiment. Building on earlier worst case bounds of Hibbard and on estimates involving the degree of distinguishability, it …
This note studies the evasion version of a linear differential game in which one controlled object seeks to avoid coincidence with another under nonanticipative choice of controls. For the system defined by a constant matrix and convex compact control sets, the authors formulate a sufficient geometr…
