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 introduces sampled Boolean functions over finite Galois fields and defines their discrete Laplace, or Laplace-Galois, transform as a tool for analyzing sequential machines. It gives direct and inverse transform formulas, including a residue-based inversion method, and states basic operati…
This review discusses P. S. Bondarenko’s monograph on finite difference algorithms for the approximate integration of differential equations, with particular attention to the distinction between abstract algorithms using exact arithmetic and real algorithms using fixed precision arithmetic with roun…
This paper defines the capacity of a subset of an input signal space for a statistical channel given by a family of probability measures, and relates this quantity to distinguishability and Shannon information. It proves basic properties of capacity, including subadditivity and multiplicativity for …
This note studies lower bounds for the complexity of problems related to systems of linear equations over the field with two elements, considering both the decision problem of whether the determinant is zero and the problem of finding the solution when it is unique. Using a construction related to N…
This paper studies limiting regimes of nonlinear control systems with several scalar nonlinearities that may be discontinuous and are constrained by sector-type monotonicity conditions. Solutions are defined in an augmented sense allowing values between one-sided limits, so that sliding regimes can …
The paper addresses the problem of proving superlinear lower bounds for explicitly defined Boolean functions without imposing special restrictions on the computational basis. It constructs a family of Boolean functions by partitioning variables into logarithmic-size blocks and using distinct conjunc…
The paper extends the binary majority, or voting, function to continuous signals in order to support restoration in analog systems with parallel redundancy. Using the correspondence between logical disjunction and maximum selection, and between conjunction and minimum selection, it derives equivalen…
The paper studies limitations of universal methods for minimizing Boolean functions in disjunctive normal form, including enumeration of irredundant forms, statistical selection, and local algorithms based on neighborhoods of conjunctions. It defines measures of difficulty such as the number of irre…
The paper addresses adaptive automatic control for a dynamic plant whose gain varies over a wide range but changes slowly relative to the transient process. It develops a variable-structure control law in which the switching hyperplane is not fixed, but selected according to an estimate of the curre…
The paper argues that emerging limits in computer performance arise less from arithmetic speed than from memory access, especially the time required to read program instructions. Drawing on experience with BESM-6 and other Soviet machines, the authors propose separating numeric and program memory, e…
This note addresses the synthesis of nonlinear control laws for an automatic system of order n, where added nonlinear elements are intended to compensate existing nonlinear effects and improve dynamic behavior. Using a canonical transformation, the system is rewritten in variables that separate most…
The paper studies absolute stability and dissipativity of a nonlinear control system whose linear part is Hurwitz and whose single differentiable nonlinearity satisfies sector and derivative bounds. It derives frequency-domain criteria, expressed through the transfer function of the linear part and …
The paper studies the circuit complexity of Boolean operators, especially linear Boolean operators, over the basis consisting of addition modulo 2, conjunction, and constants. It proves that the complexity of any Boolean operator is at least the complexity of its linear part, and uses this to reduce…
This paper studies a two-level model in which a regulating device alters the game interaction among a population of two-action automata so that the average fraction choosing one action approaches a prescribed value. Using computer simulations of 50 automata with linear tactics, the authors test a co…
This paper studies absolute stability of discrete pulse automatic control systems with finitely many degrees of freedom and a single scalar nonlinear block, represented by a nonlinear difference equation. Under sector and slope restrictions on the nonlinearity and spectral assumptions on the linear …
The paper addresses operability checking and fault diagnosis for finite automata with memory when the class of possible faulty modifications need not be exclusive, minimal, or strongly connected. It formalizes compatibility, essential faults, and distinguishability in terms of like-named and equival…
This paper establishes a sufficient frequency-domain criterion for the absolute stability of multiconnected pulse systems with a stable linear pulse part and multiple nonlinear elements whose sector-bounded characteristics may vary with time. The system is represented by a vector difference equation…
This note studies a class of Post calculi defined by productions of types I and IIa, motivated by their relation to formal languages, finite automata, and a conjecture of Büchi. After recalling definitions and known results on normal calculi and calculi with type Ia productions, it proves that every…
The paper introduces the concept of double invariance in automatic control systems, defined as the case where conditions ensuring invariance of a controlled coordinate with respect to specified external actions also make the system operator independent of plant parameters. Starting from a general sy…
This note studies the structure of error-correcting codes for asymmetric channels over a finite field, where only a specified subset of symbols is subject to distortion. It defines admissible asymmetric errors, introduces an associated distance for pairs of signals, and proves a necessary and suffic…
The paper studies the derivability problem for predicate calculi without function symbols, focusing on formulas and sequents containing only unary predicate variables. It constructs explicit algorithmic transformations from a previously established undecidable class of sequents to several restricted…
This paper presents a matrix-based method for constructing and analyzing binary cyclic error-correcting codes, using the cyclic properties of square matrices as an alternative to the usual polynomial ideal formulation. It defines check and quasi-check matrices generated by repeated application of a …
This paper studies prediction of binary discrete-time random processes when the correlation or spectral function is not known in advance. For homogeneous Markov processes with finite dependence length and a limiting distribution, it derives the minimum attainable mean prediction error over Boolean f…
The paper addresses abstract synthesis for an extended language of regular expressions that includes intersection and complementation, for which earlier synthesis procedures were not directly algorithmic. It defines a finite basis of regular expressions through derivative-like equations and gives an…
This paper analyzes parallel decoding for discrete stationary channels with independent noise as a way to reduce the computational burden of optimal decoding, whose complexity grows exponentially with block length. The method divides the received word into subwords, enumerates candidate input subwor…
This paper studies the characterization of events representable by finite probabilistic automata, extending Rabin’s observation that such events form a broader class than regular events. It formulates representability in terms of finite-dimensional stochastic vector functions and gives necessary and…
This paper extends Yakubovich’s matrix inequality method to discrete difference equations describing automatic systems with a single pulse controller and a scalar nonlinearity satisfying sector and derivative bounds. It formulates a frequency-domain sufficient condition, involving the transfer funct…
This paper addresses the construction of right inverse operators for controlled plant operators in automatic control, a problem arising in particular in invariance design for nonlinear systems. It represents a plant by a finite block construction consisting of integration, differentiation, delay, an…
The article presents a method for analyzing finite automata by treating their transition matrices as multi-terminal networks over an algebra of events, with operations of union, product, and iteration. It proves that eliminating a terminal preserves the complete conductances between all remaining te…
This paper examines invariance in model-based non-search self-adjusting control systems whose plant parameters may vary at rates comparable to system transients and then become constant. Using a differential-equation representation of the plant, controller, adaptation laws, and reference model, the …
This paper studies the synthesis complexity of depth two gate circuits for Boolean matrices containing undetermined entries, motivated by control systems whose outputs need not be specified on forbidden input combinations. It formalizes completions of such matrices, proves a covering lemma for verti…
The paper proposes a domain-splitting variant of the sweep method for implicit finite-difference solution of one-dimensional heat-conduction and gas-dynamics problems when a full multidimensional time layer cannot conveniently be held in operative memory. The method transmits different interface dat…
The paper studies how the topology of an automaton constrains its computational behavior, introducing the notions of a medium, its capacity, modeling, and strong modeling. It defines automata as networks of delayed elements and proves limitations on simulating automata embedded in media of higher ca…
This paper studies analytic criteria for positivity of real functions arising in automatic control and circuit synthesis, including Popov-type absolute stability conditions and realizability of positive real network functions. It reformulates positivity in terms of stability of the parameter-depende…
The paper studies the difficulty of recognizing, by a Boolean characteristic function, whether a given set of elementary conjunctions is the reduced disjunctive normal form of some Boolean function in n variables. It represents subsets of elementary conjunctions as vertices of a Boolean cube with 3^…
This paper describes an addressing method for machine dictionaries in which compressed word codes are used directly as random-access memory addresses. It outlines a letter-by-letter compression procedure based on shifted modulo-2 addition of letter codes chosen with regard to probabilistic and stati…
This paper studies binary codes for channels in which symbols may be deleted, inserted, or reversed, extending the usual substitution error model. It formulates deletion and insertion correction in metric terms, proves equivalences among correction notions for fixed length codes, and derives bounds …
This note proposes a cutting-plane algorithm for integer linear programming problems whose integer variables are Boolean. The method reduces the original maximization problem to a sequence of canonical feasibility problems with thresholded objective value, then solves each by lexicographic maximizat…
The paper proposes an algorithm of centered sections for approximate minimization of Lipschitz convex functions on convex polyhedra, using gradient direction evaluations to cut away regions that cannot contain a minimizer. It develops the method first in two dimensions, where centroid cuts give geom…
This paper extends the characteristic function method for valve-contact multipoles to networks that include make contacts of internal relays, allowing feedback and multicycle transient operation while excluding break contacts of internal relays. It proves that, for fixed external relay states and ap…
This note describes a construction of finite automata with growing memory that are asymptotically optimal in arbitrary stationary random environments, and studies zero-sum games between two automata of this type. The analysis expresses play probabilities through the induced Markov chain and uses asy…
