Kalman-Mesarovic nonstationary realization in terms of Rayleigh-Ritz operator

The paper outlines the methodology underlying the Kalman-Mesarovic realization for dynamic systems with equations of state in the class of linear nonstationary ordinary differential equations. In this sense, the key approaches to solving problems of realization theory in terms of the Rayleigh-Ritz operator are defined. The study was sponsored by the Russian Fund for Basic Research (Grant No. 05-01-00623), Program of Basic Research No. 22 of the Presidium of the Russian Academy of Science, the Grant of the President of the Russian Federation on the State Support of Scientific Schools of the Russian Federation (Grant No. NSh-9508.2006.1). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 82–90, January–February 2007.     

From Kalman—Mesarovic realization to a normal-hyperbolic linear model

The principles of the methodology are formulated, which underlie the procedures of the Kalman—Mesarovic realization for dynamic systems with state equations in the class of autonomous linear differential equations in the normalized Frechet space. In this connection, the key approaches to the solution of classical problems of realization theory regarding linear dissipation models of normal-hyperbolic type are interpreted. The study was sponsored by the Russian Fund for Basic Research (grant No. 05-01-00623), the “Integration” Russian Federal Target Program (grant No. B0077), and the Program for Basic Research of the Presidium of the Russian Academy of Sciences (program No. 19, project 2.5). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 137–157, November–December 2005.     

A type of isomorphism between linear and nonlinear signature analyzers

It is proved that an automaton that is state and input isomorphic to a linear primitive automaton is only state isomorphic to the latter automaton. A criterion of state isomorphism between an irredundant signature analyzer (SA) and some linear SA with the zero initial state is found. This work was supported by the Russian Foundation for Basic Research under grant 98-01-00113. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 41–46, July–August, 2000.     

Stabilization of Nonlinear Dynamic Systems Using the System State Estimates Made by the Asymptotic Observer

Consideration was given to asymptotic stabilization of the equilibria of nonlinear dynamic systems using the dynamic output feedbacks, that is, the feedbacks in the estimate of system state made by the asymptotic observer. Presented were the basic methods of constructing the asymptotic observers for the nonlinear dynamic systems with control and the approaches to system stabilization using the system state estimate made by the observer.__________Translated from Avtomatika i Telemekhanika, No. 7, 2005, pp. 3–42.Original Russian Text Copyright © 2005 by Golubev, Krishchenko, Tkachev.This work was supported by the Russian Foundation for Basic Research, project no. 05-01-00840, Grant for State Support of the Leading Scientific Schools, project no. NSh-2094.2003.1, and project no. UR.03.01.141 of Section 1.2 “Russian Universities” of the Subprogram “Basic Research” of the Departmental Scientific Program “Development of the Scientific Potentialities of the Higher School” of the Federal Education Agency of the Russian Federation.     

Stability of Vector Problems of Integer Optimization: Relationship with the Stability of Sets of Optimal and Nonoptimal Solutions

Several types of stability against perturbations of vector criterion coefficients are analyzed from the same point of view for a vector integer optimization problem with quadratic criterion functions. The concept of stability is defined. Necessary and sufficient conditions are formulated and analyzed for each type of stability. The topological structure of the sets of initial data on which some solution remains optimal is described. The study was supported from the State Fund for Basic Research of Ukraine (Grant F7/275-2001). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 90–100, July–August 2005.     

New Theory of Cooperative Games

The paper proposes a new theory of cooperative games based on the notions of conflict equilibrium alone. In this theory, the solution always exists, and it is often unique. The study was sponsored by the Russian Fund for Basic Research, Project No. 03-01-00329, and according to the OITVS Program of the Russian Academy of Sciences, Project No. 1–3. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 156–167, September–October 2005.     

Methods for formation of features of tree-like structures on fundus images

A fundamental problem of computer diagnostics is the detection of a vascular system on an image and the determination of its local and global parameters. Methods for tracing vessels and estimating their diagnostic features based on a mathematical model of a fundus fragment are described. This work was supported by the Ministry of Education of the Russian Federation, Administration of Samara Region, the U.S. Civilian Research and Development Foundation in the framework of the Russian-American program “Basic Research and Higher Education” (CRDF project no. SA-014-02), and by the Russian Foundation for Basic Research, project no. 03-01-00642.     

Backward representation of Markov jump processes and related problems. I. Optimal linear estimation

Abstrat The Martingale representation for a class of special Markov jump processes in reverse time is derived and applied to study optimal linear filtering and smoothing of states of nonlinear observation systems. Original Russian Text ? A.V. Borisov, 2006, published in Avtomatika i Telemekhanika, 2006, No. 8, pp. 51–76. This work was supported in part by the Russian Foundation for Basic Research, project no. 05-01-00508a, and OITVS Project “Fundamental Algorithms for Information Technologies,” Russian Academy of Sciences, project no. 1.5. This paper was recommended for publication by A.I. Kibzun, a member of the Editorial Board     

Formulation and analysis of problems for dynamic systems of inhomogeneous two-phase media

A mixed initial—boundary-value problem with a discontinuous solution for a system of dynamic equations of water-saturated soil consolidation is analyzed. The classical solution is proved to be unique. Error estimates are obtained for time-continuous and fully discrete approximate generalized solutions constructed by the finite-element method. The study was sponsored by the State Fund for Basic Research (GFFI), Grant No. F7/307-2001. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 85–100, November–December 2005.     

Experimental investigation of forecasting methods based on data compression algorithms

We suggest and experimentally investigate a method to construct forecasting algorithms based on data compression methods (or the so-called archivers). By the example of predicting currency exchange rates we show that the precision of thus obtained predictions is relatively high.Translated from Problemy Peredachi Informatsii, No. 1, 2005, pp. 74–78.Original Russian Text Copyright © 2005 by Ryabko, Monarev.Supported in part by the Russian Foundation for Basic Research, project no. 03-01-00495, and INTAS, Grant 00-738.     

An integrated approach to evaluating the mutual influence of attributes in test recognition

The problem of estimating the weight coefficients of attributes used in intelligent decision-support systems is considered. A procedure is proposed to estimate the relative significance of attributes based on special relative attribute-importance measures. The properties of the procedure are proved and illustrative examples are given. The study was sponsored by the Russian Foundation for Basic Research (project No. 07-01-00452, No. 09-01-99014-r_ofi). Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 127-135, May–June 2009.     

The concept of and search for the fair distribution in cooperative games

Well-known conflict equilibria are used to formulate the concept of fair distribution, and a technique is proposed to find it in an arbitrary cooperative game. Any cooperative game is shown to have only one fair distribution, which can always be found from the formulas of conflict equilibrium theory. The study was carried out in line with the OITVS RAN program (Project No. 1-3) and was sponsored by the Russian Foundation for Basic Research (Project No. 06-01-00821). Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 131–141, November–December 2008.     

Expansion of classical noncooperative equilibrium and program differential games

A generalization of the classical noncooperative equilibrium is proposed. The new equilibrium exists in a broader class of games and problems of accepting proposals than the classical equilibrium. Applications of this equilibrium to program differential games are considered. This study was supported by the Russian Fund for Basic Research, Projects Nos. 97-01-00123 and 97-01-00962. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 105–115, July–Ausust, 2000.     

The Grey-Rankin bound for nonbinary codes

The Grey-Rankin bound for nonbinary codes is obtained. Examples of codes meeting this bound are given. Original Russian Text Ş L.A. Bassalygo, S.M. Dodunekov, V.A. Zinoviev, T. Helleseth, 2006, published in Problemy Peredachi Informatsii, 2006, Vol. 42, No. 3, pp. 37–44. Supported in part by the Russian Foundation for Basic Research, project no. 06-01-00226.     

Comparison of human face matching behavior and computational image similarity measure

Computational similarity measures have been evaluated in a variety of ways, but few of the validated computational measures are based on a high-level, cognitive criterion of objective similarity. In this paper, we evaluate two popular objective similarity measures by comparing them with face matching performance in human observers. The results suggest that these measures are still limited in predicting human behavior, especially in rejection behavior, but objective measure taking advantage of global and local face characteristics may improve the prediction. It is also suggested that human may set different criterions for “hit” and “rejection” and this may provide implications for biologically-inspired computational systems. Supported by the National Basic Research Program of China (Grant No. 2006CB303101), the National Natural Science Foundation of China (Grant Nos. 60433030, 30600182 and 30500157), and the Royal Society     

Two-level self-diagnosis model for bus-topology distributed systems

Conclusion  We have justified the two-level self-diagnosis model, in which faulty CE are detected by self-diagnosis on the subsystem level and non-self-diagnosable subsystems are detected by diagnosis on the whole system level. The results of system-level self-diagnosis can be used to decide on the validity of subsystem-level self-diagnosis results. Self-diagnosability indices are estimated for the proposed model. The self-diagnosis time for the proposed model is substantially shorter than for the (one-level) model of [5]. We should also note that the proposed self-diagnosis model can be used as a basis for the development of a fault-tolerant distributed computing system with reconfigurable structure. The computing system can use the self-diagnosis results to reconfigure its structure. The study was supported by the Russian Foundation for Basic Research, grant No. 93-01-00589. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 157–165, January–February, 1998.     

Associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node to a graph

This paper proposes a new associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node with all its incident edges to a graph. This algorithm is represented as the InsertVert procedure implemented on a model of an associative parallel system of the SIMD type with vertical processing (a STAR machine). The correctness of the procedure is proved and its time complexity is estimated. This work was supported by the Russian Foundation for Basic Research under grant 03-01-00399. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 19–31, January–February 2006.     

On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms

We present a time algorithm finding a minimum feedback vertex set in an undirected graph on n vertices. We also prove that a graph on n vertices can contain at most 1.8638 ⁿ minimal feedback vertex sets and that there exist graphs having 105 ^n/10≈1.5926 ⁿ minimal feedback vertex sets. Preliminary extended abstracts of this paper appeared in the proceedings of SWAT’06 [29] and IWPEC’06 [18]. Additional support of F.V. Fomin, S. Gaspers and A.V. Pyatkin by the Research Council of Norway. The work of A.V. Pyatkin was partially supported by grants of the Russian Foundation for Basic Research (project code 05-01-00395), INTAS (project code 04–77–7173). I. Razgon is supported by Science Foundation Ireland (Grant Number 05/IN/I886).     

Modeling hexagonal constellations with Eisenstein-Jacobi graphs

A set of signal points is called a hexagonal constellation if it is possible to define a metric so that each point has exactly six neighbors at distance 1 from it. As sets of signal points, quotient rings of the ring of Eisenstein-Jacobi integers are considered. For each quotient ring, the corresponding graph is defined. In turn, the distance between two points of a quotient ring is defined as the corresponding graph distance. Under certain restrictions, a quotient ring is a hexagonal constellation with respect to this metric. For the considered hexagonal constellations, some classes of perfect codes are known. Using graphs leads to a new way of constructing these codes based on solving a standard graph-theoretic problem of finding a perfect dominating set. Also, a relation between the proposed metric and the well-known Lee metric is considered. Original Russian Text 7sC C. Martínez, E. Stafford, R. Beivide, E.M. Gabidulin, 2008, published in Problemy Peredachi Informatsii, 2008, Vol. 44, No. 1, pp. 3–14. Supported in part by the Spanish Comision Interministerial de Ciencia y Tecnologia (CICYT), Grant TIN2004-07440-C02-01, and the Research Program of the Universidad de Cantabria, Grant 30.640.VI07. Supported in part by the Russian Foundation for Basic Research, project no. GFENa-05-01-39017.     

Mapping timed cause-effect structures into timed petri nets

Conclusion The problem of inverse mapping of Petri nets into CES remains an interesting open question. Raczunas [5] claims that it is not for every PN that a strictly equivalent CES exists. He accordingly proposes weak equivalence of this mapping. Kotov [6] defines a topologically structured subclass of PN—regular PN. The subclass of regular PN has the same cardinality as the class of all PN in the sense of behavioral equivalence. It is therefore relevant to compare the class of regular PN with CES. The study was partially financed by the Russian Foundation for Basic Research, grant No. 93-012-986. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 44–54, March–April, 1997.