Solution of a Matrix Problem on a Mathematical Safe for Locks of the Same Kind. I

A mathematical safe problem is first formulated in a general form. The case of a set of locks that are of the same kind and are arranged in the form of a rectangular matrix is considered. Locks are considered to be of the same kind if their states are specified by numbers from the class of residues to a definite modulus. In the case of a prime modulus, a complete solution is provided. All the results obtained are illustrated by examples.__________Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 155–167, March–April 2005.     

Testable design of AND–EXOR logic networks with universal test sets

This paper presents a testability enhancement technique suited for AND–EXOR based logic networks that facilitates easy detection of stuck-at and bridging faults by a universal test set. Both cascaded and tree implementations of the EXOR-part are considered. The AND–EXOR based circuit implemented with a cascaded EXOR-part requires a universal test set of size (2n + 6) for an n-variable function implementation. For Generalized Reed–Muller (GRM) implementation, this test set detects all single stuck-at and bridging faults (both OR-type and AND-type) and also large number of multiple bridging faults. For an Exclusive-OR Sum-of-Products (ESOP) implementation, a few single bridging faults may remain untested under this test set, occurrence of which can be minimized by employing an appropriate design and layout technique. Next, it is shown that an AND–EXOR network with a tree-based EXOR-part can be tested for similar faults by a universal test set of size (2n + 8). This paper also solves an open problem of designing a universal test for a tree-based AND–EXOR circuit. Since the EXOR-tree has depth of (log₂s+1), where s is the number of product terms in the given AND–EXOR expression, this tree-based design reduces the circuit delay significantly compared to cascaded EXOR implementation. In both the cases, the test set can be stored in a ROM on-chip for built-in self-test (BIST) purposes. For several benchmark circuits, the universal test set is found to be much smaller in size than the ATPG-generated test sets.     

A thermodynamic description of the Al–Ca–Zn ternary system

A comprehensive thermodynamic database of the Al–Ca–Zn ternary system is presented for the first time. Critical assessment of the experimental data and re-optimization of the binary Al–Zn and Al–Ca systems have been performed. The optimized model parameters of the third binary system, Ca–Zn, are taken from the previous assessment of the Mg–Ca–Zn system by the same authors. All available as well as reliable experimental data both for the thermodynamic properties and phase boundaries are reproduced within experimental error limits. In the present assessment, the modified quasichemical model in the pair approximation is used for the liquid phase and Al_FCC phase of the Al–Zn system to account for the presence of the short-range ordering properly. Two ternary compounds reported by most of the research works are considered in the present calculation. The liquidus projections and vertical sections of the ternary systems are also calculated, and the invariant reaction points are predicted using the constructed database.     

Diffusion approximation and filtering for a queueing system with repeats

A single-channel Markov queueing system with repeats is considered. The number of waiting customers is shown to converge to an Ornstein-Uhlenbeck process. Filtering problems for this queueing system are considered.Translated from Kibernetika, No. 2, pp. 84–90, 104, March–April, 1990.     

Conflict controlled processes with discontinuous trajectories

Linear differential games with pulse control of players, which is represented by the Dirac delta-function, are analyzed. For this class of games, the sufficient conditions for the solvability of the approach problem are derived. The problems are analyzed based on the method of resolving functions. The result is exemplified by a pursuit game with a simple motion.The study was sponsored by the State Fund for Fundamental Research (DFFD), Grant No. F7306-2001, Project 01.07013, and by the Scientific and Technical Center of Ukraine (NTTsU).Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 15–29, November–December 2004.This revised version was published online in April 2005 with a corrected cover date.     

Language recognition by two-way deterministic pushdown automata

It is proved that any bounded context-free language can be recognized by a two-way deterministic automaton with a finite-rotary counter.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 177–181, November–December 2004.This revised version was published online in April 2005 with a corrected cover date.     

Models of Computation of a Multialternative Prediction Graph on the Basis of Analytical Estimates

Problems of the theory of construction and computation of prediction graphs are considered. Questions of solution of the problem of quantitative analysis of prediction graphs are investigated.__________Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 91–106, March–April 2005.     

Optimization of stability estimates of systems of stochastic differential-difference equations

Estimates of stability characteristics are considered for delayed linear stochastic differential-difference systems. The estimates are optimized on the class of positive definite matrices.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 38–43, July–August, 1992.     

Collective Hamiltonian method in optimal control problems

Some geometrical aspects of Hamiltonian systems arising in optimal control problems are considered.Translated from Kibernetika, No. 2, pp. 73–77, March–April, 1989.     

Minimization of combinational multiplexor/selector automata (MS-automata and equivalent transformations of their trees)

Implementation of arbitrary combinational multiplexor/selector automata is considered. Minimization methods and an algorithm for minimizing the multiplexor tree are proposed.Translated from Kibernetika, No. 5, pp. 49–53, September–October, 1989.     

Methods to find the most preferred element on a set of Pareto-optimal decisions

Stochastic interactive procedures are considered, based on paired comparison of efficient solutions with parametrization of the Pareto-optimal set. The convergence conditions of these procedures are analyzed.Translated from Kibernetika, No. 5, pp. 34–37, September–October, 1990.     

Manipulation aspect of databases: The composition approach

Database manipulations are formalized as denotate-preserving functions. The main issues considered are the synthesis of manipulation operations and the construction of a universal kernel of data-manipulation languages.Translated from Kibernetika, No. 6, pp. 105–113, November–December, 1989.     

Complexity of algorithms that construct subsets of data from formal definitions

Polynomial-time algorithms that construct subsets of data from formal logical definition are considered.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 49–57, September–October, 1991.     

Net models of discrete information transducers. I

Dynamic net models of a special kind — discrete process generators — are considered. Their relation to automata, Petri nets, partially commutative monoids, and the theory of traces is examined.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 83–90, September–October, 1991.     

Assessment of reconfiguring algorithms for MIMD architectures

Some issues of reconfigurable computing systems with MIMD architecture are considered. A number of reconfiguring algorithms are analyzed by simulation from the aspect of the attainable fault tolerance.Translated from Kibernetika, No. 2, pp. 35–41, March–April, 1990.     

Some properties of multidimensional renewal processes

Multidimensional Poisson renewal processes are considered. Analytical expressions are derived for the main characteristics of the processes and some properties of the multidimensional renewal equations and renewal functions are examined.Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 99–106, January–February, 1992.     

Extremal problems with rare events. I

The paper considers optimization of systems with rare events causing large damage. A number of propositions are stated concerning uniform convergence of stochastic iterative optimization algorithms and some numerical results are considered.Translated from Kibernetika, No. 5, pp. 55–58, September–October, 1990.     

Solution of single-product nonlinear programming problem with joint constraints

Single product, single factor optimal planning problems with a decreasing cost function and joint constraints are considered. Existence conditions are obtained and effective algorithms for the construction of optimal programs are proposed.Translated from Kibernetika, No. 1, pp. 76–80, January–February, 1990.     

Portrait of the inverse of a sparse matrix

Sparse matrices with sparse inverses are considered. The addresses of the nonzero elements in the inverse matrix are calculated from the positions of the nonzero elements of the original matrix.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 31–38, July–August, 1992.