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 paper studies inversion problems for asynchronous partial finite automata, motivated by parallels with unique decodability and finite-memory decoding in coding theory. It defines several forms of unambiguity, including one-to-one behavior on finite words, weak one-to-one behavior, and one-to-on…
The paper develops a rapid descent algorithm for constrained minimization of a differentiable function over a bounded domain defined by differentiable convex inequalities. It describes procedures for finding an interior feasible point, minimizing along a feasible direction, and constructing descent …
This paper examines the relationship between deterministic and statistical formulations of optimal synthesis for automatic control systems subject to continuously acting disturbances. It compares invariant control systems, characterized through K(D)-images of disturbance functions, with Wiener optim…
The paper addresses the determination of the phase-space position of a nonlinear controlled system when the initial phase coordinates are unknown, only one phase coordinate can be measured, and the origin of that measured coordinate is itself unknown. The system is reduced from higher-order nonlinea…
The paper studies enumeration problems for planar graphs and planar realizations motivated by the synthesis of logical and contact circuits. It develops combinatorial encodings of plane rooted trees as “rivers” and of certain planar structures as rosettes, using these constructions to bound the numb…
This note studies the construction of fault tests for contact circuits formed as bounded block diagrams, where blocks are connected in series and each block has a uniformly bounded number of contacts depending on distinct variables. It introduces a structural condition under which unit open-circuit …
This note studies the problem of determining monotone Boolean functions from values computed at as few vertices of the Boolean cube as possible. It defines resolving sets in terms of upper zeros and lower ones, then analyzes a class of local algorithms of rank k that choose subsequent evaluation poi…
The paper studies limitations on extracting computational data from convergence and differentiability assertions in constructive mathematical analysis. It proves that in any constructive metric space with at least two distinct points, no algorithm can transform every sequence converging to a fixed p…
This paper addresses the problem of organizing sequentially arriving information in computer memory so that records can be searched and inserted efficiently according to a numerical key. It proposes a reference table structured as an admissible binary search tree, in which the heights of the left an…
This paper justifies a fictitious-domain method for the numerical solution of a Dirichlet problem for the Poisson equation in a plane domain bounded by coordinate-parallel line segments. The method embeds the domain in a rectangle, solves an auxiliary transmission problem with a large parameter on t…
This paper addresses finite two-person zero-sum positional games with perfect recall and develops a reduction of the search for optimal behavior strategies to a constrained matrix game. The method constructs an information tree for each player, preserving the partial ordering of that player’s inform…
The paper proposes interpreting p-adic numbers as p-ary signal sequences, with multiplication by p corresponding to a delay element, in order to apply p-adic algebra and analysis to the study of sequence-transforming circuits. It outlines basic p-adic notions, defines functional elements such as mod…
The paper compares the minimal number of contacts needed to realize monotone Boolean functions by contact circuits using only closing contacts with the minimum for arbitrary contact circuits allowing opening contacts. It studies the functions expressing that at least two of n variables are equal to …
The paper examines how control systems with fixed, or rigid, structures can be synthesized so that they behave equivalently to self-adjusting systems when plant characteristics are altered by disturbances or by internal parameter changes. Using transfer-function analysis in the limit of large gain, …
This paper develops a statistical formulation of approximate computation, using quadrature formulas for definite integrals as the main example, under the assumption that sampled function values contain unavoidable random errors. Treating quadrature as an estimator of a parameter-dependent integral, …
The paper studies the relationship between finite automata and a language of monadic predicate logic in which earlier restrictions on object and predicate quantifiers are removed. It develops a normal form for formulas and uses a topological interpretation via Cantor space, introducing homogeneous s…
This paper studies algorithmic decision problems for automata presented by finite systems of generators, inputs, and defining relations, treating automata as algebraic systems. It shows that presentations can be transformed into closed systems of defining relations, yielding canonical word forms and…
This paper studies the synthesis complexity of Boolean control systems represented as circuits of functional elements, using average and maximum numbers of excited elements, interpreted for example as circuit power, rather than total element count. It defines corresponding Shannon-type functions ove…
This note studies how far the complexity of an arbitrary irredundant disjunctive normal form can exceed that of a minimal disjunctive normal form for the same Boolean function. Using recursive constructions of Boolean functions and associated pairs of irredundant forms, it establishes lower and uppe…
This paper studies finite automata operating in random environments that penalize actions with specified probabilities, formulating their behavior as Markov chains under ergodicity assumptions. It analyzes automata with a linear tactic, deriving the expected penalty and showing that in a stationary …
The paper studies the complexity of realizing monotone Boolean functions of n variables by circuits of functional elements for conjunction and disjunction. It refines Shannon’s decomposition method by estimating the number of distinct monotone subfunctions that can actually arise after substituting …
The paper develops an algebraic framework for potential-pulse objects, understood as two-state logical objects whose time behavior includes stable potentials, impulses, and transitions. It defines a six-symbol alphabet for potential-pulse logical variables, formulates local temporal rules, and intro…
The paper studies systems of Boolean algebra equations whose coefficients are multivalued, represented as partially ordered segments of Boolean functions, and organized into complete coalitions of coefficient tuples. It defines coalitions of equations and their particular, general, coalitionary, and…
This paper addresses qualitative analysis of electrical circuits containing both contacts and elements of finite conductance, where the task is to determine whether conductance between nodes is zero, finite, or infinite. It models these values using the three-element algebra of Łukasiewicz with max …
This note studies time-optimal control for differential systems and addresses gaps in the justification of dynamic programming for such systems, especially when the value function is not continuously differentiable. It formulates sufficient conditions for optimality using a refined dynamic programmi…
This paper develops a direct method for deriving equations for pulse automatic systems with amplitude-pulse modulation of the second kind, where the pulse element periodically closes and opens the control circuit. Using the discrete Laplace transform, the closed-loop system is formulated as a Fredho…
This paper studies one-to-one alphabetic coding without memory over a finite output alphabet, focusing on variable-length codes and the conditions under which decoding can be performed with finite delay. Using a finite-state graph associated with a coding system, it gives necessary and sufficient gr…
The paper addresses the construction of transfer matrix functions for complex multiloop automatic control systems, where direct and feedback couplings between loops make purely algebraic derivations cumbersome and error prone. It proposes representing opened multiloop systems as cascades of multi-te…
This paper analyzes round-off errors in the numerical solution of consistent systems of linear algebraic equations with symmetric matrices, focusing on the Cholesky method for floating-point binary machines. Under explicit assumptions on errors in arithmetic operations, it derives bounds for the res…
The paper studies the realization of arbitrary Boolean functions of n variables by depth two networks composed of threshold elements, focusing on an upper bound for the number of first layer elements needed. It formulates the synthesis problem as a system of inequalities over threshold coefficients …
The paper addresses the time-optimal control of a linear dynamical system whose control values lie in a closed bounded convex polyhedron, under a general-position condition previously used in Pontryagin-type optimal control results. It recalls that optimal controls are extremal and then gives a cons…
This note proves the minimality of contact circuit realizations for a class of Boolean functions in an arbitrary number of variables, extending known minimality results beyond previously studied cases. The function considered is the chain function, whose perfect disjunctive normal form is analyzed t…
The paper studies the functional capabilities and synthesis of discrete threshold elements whose outputs are determined by the sign of an integer weighted sum of binary inputs. It reformulates realizability of logical functions as separation of vertices of an n-dimensional unit hypercube by a hyperp…
The paper studies the synthesis of oriented Boolean circuits whose chain conductivities are computed as in contact circuits, while circuit conductivities are combined by addition modulo 2, termed R-circuits. It develops a construction based on graphs associated with systems of pairwise orthogonal Bo…
The paper develops a general synthesis method, the principle of local coding, for realizing selected classes of Boolean functions and operators by circuits of functional elements in a finite weighted basis. It formalizes codings in which the value of an operator on an input is determined from a shor…
This paper studies effective criteria for recognizing unique decipherability, bounded decoding delay, and synchronization in code systems defined by paired dictionaries of messages and code words. It introduces right and left classes generated from a code dictionary and uses them to give finite test…
This paper analyzes structural noise immunity in a class of closed dynamic systems with negative feedback, including automatic control systems whose elements may be affected by bounded disturbances at different points in the chain. Using transfer-function relations for disturbed and undisturbed elem…
The paper studies the Shannon complexity of Boolean functions realized by circuits and superpositions over bases that include zero weight nontrivial elements and positive weight negation. For a basis with free conjunction, disjunction, and constants, and unit cost negation, it introduces inversion c…
The paper studies simplification of reduced disjunctive normal forms of Boolean functions by algorithms of finite index, in a setting where no such algorithm can always construct a minimal form. It defines a partial order on algorithms by the amount of simplification they achieve and introduces k-ma…
The paper studies the asymptotic complexity of representing Boolean functions by formulas over bases that include nontrivial linear formulas of zero weight, together with conjunction and, when needed, negation of unit weight. Using Post’s classification of closed classes of linear Boolean functions,…
The paper studies equivalent transformations of contact-rectifier circuits, extending earlier work on contact circuits and focusing on whether a finite complete system of transformation rules can exist for this broader class. It defines equivalence by equality of conductance between corresponding or…
This paper addresses automatic optimization in complex control systems with many working parameters, especially when the objective function is unknown, time dependent, and accessible only through experiment. It contrasts blind search and local search methods with a proposed nonlocal “ravine” method,…
This note studies the extended monadic predicate calculus over the natural numbers with successor and predicate variables, using its connection with finite automata. It addresses questions posed by Tarski concerning decidability of the theory and definability of addition, and proves that every formu…
This note addresses the integration of potential-impulse forms used to describe discrete electronic circuits whose operation depends on changes in logical variables. It develops an algebraic method that represents each impulse conjunction as a pair of Boolean constituents and incorporates forbidden …
This paper studies when messages encoded by a variable length coding system can be decoded by a finite automaton, including under disturbances that may shift the automaton into an incorrect state or desynchronize the input. It defines stable and self-adaptive automata and proves that an ordinary dec…
The paper studies coding by discrete devices with finite memory without requiring synchronization between input and output, generalizing usual memoryless coding and finite automaton models. It defines finitely determined operators and finitely enumerable sets of words, relates them to finite-state s…
This paper examines whether the invariance principle for linear automatic control systems with constant parameters can be extended to systems whose parameters vary in time. It reformulates parameter deviations as internal disturbances and reduces the variable-parameter system to an equivalent consta…
The paper addresses the optimization of programs for complex logical problems on computing machines, focusing on how program schemes can be transformed to make more efficient use of information obtained from logical conditions. It formalizes schemes in terms of logical and resultant acts, defines lo…
This note studies the asymptotic complexity of realizing Boolean functions by formulas of bounded depth over conjunction, disjunction, and negation, using the number of variable occurrences as the complexity measure. It defines nested classes generalizing disjunctive and conjunctive normal forms and…
This paper relates connected abstract automata to special partitions of free semigroups with identity. It defines automaton partitions and semigroup partitions, then proves that every automaton partition determines a corresponding connected automaton and that every connected automaton can be recover…
