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 in Computer Science & Cybernetics
This note studies completeness for functional systems that model automata, focusing on precomplete closed classes under operations such as projection, renaming, substitution, parallel composition, and feedback. For boundedly deterministic operators, the paper defines preservation properties for clas…
This note proposes a formulation of finite automata using analysis over the space of p-adic numbers, interpreting input, output, and state sequences as p-adic quantities and automaton behavior as p-adic functions. It defines p-adic logical and automaton functions, represents Mealy and Moore automata…
This paper studies the stability of computational algorithms for inverting tridiagonal regular difference equations depending on the system order. It defines classes of regular difference operators by coefficient balance and conditioning properties, proves unique solvability, and gives estimates for…
This paper addresses ill-posed inverse problems arising in mathematical physics, focusing on Fredholm equations of the first kind and the instability of recovering an unknown function from approximate data. It formulates a regularization principle using a smoothing functional composed of a residual …
This paper studies the synthesis of a class of time-varying linear automatic control systems subject to random disturbances, described by differential equations whose coefficients depend linearly on time. Extending Phillips’s method for constant-coefficient systems, it represents the output through …
The paper studies the realization of Boolean functions by formulas over finite bases, focusing on how formula length for individual functions depends on the chosen basis. It introduces a preorder and equivalence relation on bases defined by constant-factor comparison of minimal formula lengths, prov…
This paper defines a formal notion of an algorithm scheme in which operators, logical conditions, arrows, brackets, and parameters may vary over ordered sets during execution. It introduces order and alphabetic products, parameterized systems, ranks of expressions, execution semantics, and equivalen…
The paper presents a general stochastic simulation algorithm for queuing theory problems when analytic determination of system characteristics is impractical. It formulates a queuing system in terms of active and passive elements, models only the moments at which system state changes, and orders the…
This paper studies the realization of Boolean matrices by valve circuits and estimates Shannon functions for circuit complexity under restrictions on circuit depth. Using decompositions of matrices into products and disjunctions of simpler matrices, it proves an asymptotic bound for depth two circui…
This note proposes a numerical method for time-optimal control problems for systems of ordinary differential equations with possible phase and control constraints. The method assumes an initial approximate trajectory and constructs local near-optimal transfers between neighboring phase points by an …
This paper introduces games of finite automata in which players lack prior knowledge of the game conditions and adapt their pure strategies over repeated plays using only win or loss feedback. After defining such games and illustrating deterministic cases that lead to cycles or stable points, the au…
This note extends uniform methods of information transmission to more general classes of sources and channels than the independent, discrete cases. It introduces systems of dependent message segments satisfying consistency and uniform strong mixing, and systems of channels without anticipation satis…
This paper studies uniform coding problems in which the exact statistics of a discrete memoryless channel, or of a source with independent components, are not known, but belong to prescribed consistent classes. It formulates minimax notions of channel capacity with randomized encoding and of epsilon…
The paper studies algorithms for determining a resolving set of an arbitrary monotone Boolean function given by an oracle for its values, representing such algorithms as decision trees whose height measures complexity. It proves a general lower bound for the height of any tree with unique terminal i…
This paper studies how nonerasing Turing machines can compute operators on infinite input sequences when part of the tape is reserved for intermediate information that is not counted as output. It defines universal scratchpads for such computations and characterizes them, for recursive sets with inf…
The paper studies lower bounds for the complexity of contact circuits realizing the Boolean function that is true when at least two of its n variables are true. It develops structural lemmas showing that a minimal series-parallel realization can be represented by a special monotone formula built fro…
The paper studies equivalent transformations of logical networks obtained by replacing subnetworks with equivalent subnetworks, focusing on networks built from functional elements and delay elements. Extending known results for networks without delays, it proves that for every fixed number k there i…
This paper develops an approximate frequency method for determining complex steady-state motions in nonlinear impulse automatic systems when the motion can be represented by a single predominant harmonic. Extending harmonic-balance ideas, it defines an equivalent complex gain for the nonlinear impul…
This paper examines stability of established and forced processes in nonlinear pulse automatic systems, extending earlier frequency based criteria for stability of an equilibrium position in the large. By representing deviations from a given process as the state of an associated nonstationary pulse …
The paper studies the ordering of nested, multilayer computational cycles in which some layers are commutative, with the aim of minimizing the total realization time. It first proves an ordering rule for a polynomial formed from prescribed pairs of positive parameters, showing that a minimum is obta…
The paper formulates the drawing of products, especially single crystals, from a melt as an optimal control problem for systems with distributed parameters. It develops a mathematical description combining capillary surface equilibrium, heat balance, crystallization-front dynamics, anisotropic heat …
The paper studies the approximate realization of continuous functions by finite automata, extending Shannon’s counting arguments for discrete functions and Kolmogorov and Tikhomirov’s theory of epsilon entropy. It defines discrete functions that approximate continuous functions on grids and derives …
This paper examines the selection of criteria for synthesizing combined tracking systems with variable structure, focusing on the region in a switching hyperplane where a sliding mode exists for a linear object of order n. The authors formulate the system dynamics with discontinuous right-hand sides…
The paper develops a general framework for generative languages, bases, and calculi in order to study when sets of words can be strictly represented by finitely specified calculi. It introduces weak decidability and decidability conditions for generative bases and proves that, in any weakly decidabl…
This paper examines automatic control systems with variable structure for dynamical objects whose parameters vary over wide limits. It formulates a class of nth order systems with switching coefficients and derives necessary and sufficient inequalities on the switching parameters that ensure the sli…
The paper proposes a method for converting an m-row numerical code, in which a number is represented as a sum of several positional-code summands, into a single-row code more rapidly than by successive addition. It derives a digit-wise transformation that reduces the number of rows from m to the sma…
The paper studies equivalent transformations of circuits and certain automata built from logical elements, delays, addition modulo 2, constants, and feedback elements realizing periodic summation operators. It first establishes that, for circuits over any complete finite basis of functional elements…
The paper develops a general framework for algorithms that compute information about elements of finite sets, motivated by earlier procedures for simplifying disjunctive normal forms. Elements are equipped with admissible mark vectors representing known predicate values, and algorithms update these …
This paper studies absolute stability of control systems whose linear part is coupled to hysteresis or relay hysteresis nonlinearities satisfying a sector condition. It formalizes classes of hysteresis operators, including operators with positive hysteresis loop area, and derives frequency domain su…
This note develops game theoretic models for collective behavior of interacting automata, emphasizing games in which each player’s payoff depends only on a small set of neighboring players. It defines and relates several classes of games, including Nash games, K-games with simultaneous maximization …
The paper analyzes automatic control systems with variable structure in the case where the operator multiplying the discontinuous control term is not unity, causing the switching function itself to become discontinuous. Using generalized derivatives, the authors reformulate the system through contin…
This note studies a repeated two-person zero-sum game in which one player is a finite automaton and the opponent uses an arbitrary mixed strategy. By reducing the interaction to the behavior of an automaton in a stationary random environment, it analyzes a linear-tactic automaton with finite memory …
The paper extends the method of successive improvement of a feasible vector from linear programming to convex programming problems with linear equality constraints and nonnegativity restrictions, formulated as maximization of a twice continuously differentiable concave function. Using Kuhn-Tucker op…
This paper studies the size and depth of Boolean circuits for multiplying two n digit binary integers, reducing the problem to the construction of circuits for squaring. It presents an inductive construction based on representing the input as a polynomial in a power of two, evaluating the polynomial…
The paper studies a class of one-sided Turing machines whose input symbols are eventually converted into immutable output symbols, and characterizes the sequence operators realized by such machines. It defines A-machines, shows that the set of all such machines is not recursively enumerable, and com…
This paper proposes a principle for constructing combined automatic tracking systems with variable structure to improve invariance of the tracking error with respect to control actions and parameter variations. Using systems of differential equations with discontinuous right hand sides and Filippov …
The paper presents a method for automating numerical solutions of elliptic boundary-value problems on high-speed computers by replacing a nonrectangular domain with a rectangular domain decomposed into elementary rectangles, including fictitious subdomains. It formulates matching conditions across i…
This paper studies the algorithmic complexity of discrete functions computed by binary and fixed finite-state automata, measuring complexity by the tradeoff between the number of cells and operating time. It defines a complexity set for automata realizing a given function and discusses cascades and …
This paper extends a previously noted connection between memory allocation in programming and graph coloring from a restricted class of programs to a broad class described as operator schemes. It formalizes quantities, routes, storage zones, admissible transformations, and regions of action, then gi…
This paper studies stability in the large for nonlinear pulse automatic systems, including digital systems, with a nonlinear pulse element whose characteristic lies in a sector and a stable reduced continuous part. It adapts Popov’s frequency-domain approach to impulse systems by introducing truncat…
The paper studies identical transformations of regular expressions, formulated as the problem of finding complete systems of identities for algebras of regular sets over an alphabet under union, product, and closure. It constructs a finite system of identities for the algebras whose elements are reg…
This paper examines reduction of internal states in a class of finite automata, with particular attention to asynchronous automata described by transition matrices and by equations in which state changes depend on changes of input state. The authors explain how a transition matrix for an asynchronou…
Maslov studies how arbitrary canonical calculi over a given alphabet can be transformed into calculi of restricted forms while preserving derivability of words over the original alphabet. The paper proves that, although an equivalent calculus using only the original alphabet need not exist, one auxi…
This paper studies global stability of stationary sets for nonlinear discontinuous dynamical systems whose equilibrium position may be nonunique. Using Filippov-type solutions and extending Popov’s frequency-domain method, it considers systems with a stable linear part and a bounded scalar nonlinear…
This paper studies two related solvability problems for Hermitian matrix inequalities arising in automatic control, especially in Lyapunov approaches to stability of nonlinear systems. It formulates frequency-domain characteristics for the two problems and proves necessary and sufficient conditions …
This paper addresses the synthesis of analog computing and solving devices for tracking roots of systems of finite equations whose parameters vary with time. It proposes replacing conventional discrepancy working-off schemes, which can have nonzero steady-state error, with a dynamical system derived…
This paper addresses the design of automatic control systems for plants whose parameters vary over wide ranges, using variable-structure, piecewise-linear control laws. The authors analyze conditions under which a sliding mode arises on a switching hyperplane and show that, once the system trajector…
This paper studies when operators on a finite-state memory can be represented as products of simpler operators, using Lyapunov’s formalism of memory states and special form operations. It proves basic decomposition results, including representation of every operator of type n,m by products of n,1 op…
The paper studies when Boolean functions can be realized with arbitrarily high reliability by deterministic circuits built from a mixture of error-free elements and unreliable elements whose independent error probabilities are bounded below one half. Using Post’s theory of closed classes, it gives n…
The paper develops homogeneous finite difference schemes for the Poisson equation in two spatial variables with piecewise constant coefficients and interface conjugation conditions. Using an integral balance formulation, it derives grid equations for rectangular, hexagonal, and triangular meshes tha…
