Fast parallel DNA-based algorithms for molecular computation: discrete logarithm

Diffie and Hellman (IEEE Trans. Inf. Theory 22(6):644–654, 1976) wrote the paper in which the concept of a trapdoor one-way function was first proposed. The Diffie–Hellman public-key cryptosystem is an algorithm that converts input data to an unrecognizable encryption, and converts the unrecognizable data back into its original decryption form. The security of the Diffie–Hellman public-key cryptosystem is based on the difficulty of solving the problem of discrete logarithms. In this paper, we demonstrate that basic biological operations can be applied to solve the problem of discrete logarithms. In order to achieve this, we propose DNA-based algorithms that formally verify our designed molecular solutions for solving the problem of discrete logarithms. Furthermore, this work indicates that public-key cryptosystems based on the difficulty of solving the problem of discrete logarithms are perhaps insecure.     

Modified multi-component gas transport formulation with phoretic effects

The understanding of multicomponent mass transport processes is essential for modeling and optimization of many systems, such as fuel cells. The understanding of individual species behavior becomes quite significant at micro-nano scales, where average mixture models are not very accurate. Also at micro-nano scales, additional phoretic transport is present due to strong local temperature and pressure gradients, which is discussed by Chakraborty and Durst (Phys Fluids 19(8):088104-01–088104-04, 2007). To account for multicomponent mass transport, recently proposed mass transport model by Kerkhof and Geboers (AIChE J 51(1):79–121, 2005), provides a way to look into individual components. This article presents extended multicomponent mass transport equations for micro-nano scales within continuum region. The Kerkhof–Geboers theory and the modifications suggested by Chakraborty and Durst (2007) have been combined together to form a new set of equations. An extensive order of magnitude analysis has been done on the modified equations. The application of new equations to different problem situations has also been discussed. It is shown that at very small length scales and for highly diffusive transport, the phoretic transport dominates the system, thus rendering the conventional equations erroneous.     

Atomic radial basis functions in numerical algorithms for solving boundary-value problems for the Laplace equation

A numerical method for solution of boundary-value problems of mathematical physics is described that is based on the use of radial atomic basis functions. Atomic functions are compactly supported solutions of functional-differential equations of special form. The convergence of this numerical method is investigated for the case of using an atomic function in solving the Dirichlet boundary-value problem for the Laplace equation. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 165–178, July–August 2008.     

Solving combined inverse problems for multicomponent parabolic distributed systems

The paper outlines a technique to construct computational algorithms for solving combined inverse problems for multicomponent parabolic systems with main and natural inhomogeneous interface conditions. Frechet derivatives are obtained in explicit form for quadratic residual functionals to construct gradient computational algorithms. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 48–71, September–October 2007.     

Forecasting skewed biased stochastic ozone days: analyses,solutions and beyond

Much work on skewed, stochastic, high dimensional, and biased datasets usually implicitly solve each problem separately. Recently, we have been approached by Texas Commission on Environmental Quality (TCEQ) to help them build highly accurate ozone level alarm forecasting models for the Houston area, where these technical difficulties come together in one single problem. Key characteristics of this problem that is challenging and interesting include: (1) the dataset is sparse (72 features, and 2 or 5% positives depending on the criteria of “ozone days”), (2) evolving over time from year to year, (3) limited in collected data size (7 years or around 2,500 data entries), (4) contains a large number of irrelevant features, (5) is biased in terms of “sample selection bias”, and (6) the true model is stochastic as a function of measurable factors. Besides solving a difficult application problem, this dataset offers a unique opportunity to explore new and existing data mining techniques, and to provide experience, guidance and solution for similar problems. Our main technical focus addresses on how to estimate reliable probability given both sample selection bias and a large number of irrelevant features, and how to choose the most reliable decision threshold to predict the unknown future with different distribution. On the application side, the prediction accuracy of our chosen approach (bagging probabilistic decision trees and random decision trees) is 20% higher in recall (correctly detects 1–3 more ozone days, depending on the year) and 10% higher in precision (15–30 fewer false alarm days per year) than state-of-the-art methods used by air quality control scientists, and these results are significant for TCEQ. On the technical side of data mining, extensive empirical results demonstrate that, at least for this problem, and probably other problems with similar characteristics, these two straight-forward non-parametric methods can provide significantly more accurate and reliable solutions than a number of sophisticated and well-known algorithms, such as SVM and AdaBoost among many others.     

Using the effect of information delay in differential pursuit games

An approach to solving linear differential pursuit games is substantiated. It consists in generating the pursuer’s control based on the evader’s previous behavior. The results are illustrated with model soft-meeting problems. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 90–105, March–April 2007.     

Antibody-based computing: an application to the stable marriage problem

Antibodies, among other things, are important components of the immune system. This paper proposes using the specific recognition capability exhibited by antibodies for computation, in particular, for solving the stable marriage problem, which has been studied as a combinatorial computational problem. Antibody-based computation is proposed by integrating the recognition capabilities of antibodies. The computation is carried out on an array form that is suitable not only for expressing stable marriage problems, but also for further integration to antibody microarrays. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

Analysis of stability of stochastic dynamic systems under Poisson perturbations. II. Stability of solutions in quadratic mean of systems of linear stochastic differential equations under Poisson perturbations

Necessary and sufficient conditions of asymptotic stability in quadratic mean are obtained for trivial solutions of systems of linear stochastic differential equations under Poisson perturbations. Model problems are analyzed. Part I of this article is published in No. 4 (2005). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 50–66, November–December 2005.     

New means of cybernetics,informatics, computer engineering,and systems analysis

The class of combinatorial problems equivalent to the problem of determination of relative positions of n interval sequences is formulated. It is shown that an adequate mathematical model of solving a stated problem is a finite dynamic memoryless automaton and that the adequate mathematical apparatus is continuous logic. Algorithms that solve the problem are constructed. Misc  Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 173–181, May-June 2009. Original article submitted July 4, 2007.     

Expansion of weighted pseudoinverse matrices with positive definite weights into matrix power products. Iterative methods

Weighted pseudoinverse matrices with positive definite weights are expanded into matrix power products with negative exponents and arbitrary positive parameters. These expansions are used to develop and analyze iterative methods for evaluating weighted pseudoinverse matrices and weighted normal pseudosolutions and solving constrained least-squares problems. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 45–64, January–February 2007.     

Absolute approximation ratios for packing rectangles into bins

We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of bins used. All rectangles have to be packed non-overlapping and orthogonal, i.e., axis-parallel. We present an algorithm with an absolute worst-case ratio of 2 for the case where the rectangles can be rotated by 90 degrees. This is optimal provided P 1 NP\mathcal{P}\not=\mathcal{NP} . For the case where rotation is not allowed, we prove an approximation ratio of 3 for the algorithm Hybrid First Fit which was introduced by Chung et al. (SIAM J. Algebr. Discrete Methods 3(1):66–76, 1982) and whose running time is slightly better than the running time of Zhang’s previously known 3-approximation algorithm (Zhang in Oper. Res. Lett. 33(2):121–126, 2005).     

Some Continuous Models of Inventory Control

The problem of optimal control of a manufacturing process is investigated. The dynamics of the process is described by a stochastic differential equation. Two methods of solution of this problem are considered. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 175–178, May–June 2005.     

Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees

Extensive facility location models in networks deal with the location of special types of subgraphs such as paths or trees and can be considered as extensions of classical facility location models. In this paper we consider the problem of locating a path-shaped or tree-shaped (extensive) facility in trees, under the condition that existing facilities are already located. We introduce a parametric-pruning method to solve the conditional discrete/continuous extensive weighted 1-center location problems in trees in linear time. This improves the recent results of O(nlog n) by Tamir et al. (J. Algebra 56:50–75, [2005]).     

Reliability optimization of a complex system by the stochastic branch and bound method

An optimal redundancy problem is considered as a stochastic optimization problem. The mean lifetime of a network is maximized by the stochastic branch and bound algorithm. To obtain (stochastic) estimates of branches, use is made of stochastic tangent minorants and majorants of the objective functional, interchange relaxation (permutation of maximization and expectation operations), and multiple solution of auxiliary dynamic programming problems. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 129–141, May–June 2008.     

Synthesis of optimal control of dynamic systems with infinite aftereffect,a small parameter,and poisson perturbations

A methodology is obtained that makes it possible to synthesize an optimal control for stochastic systems of functional-differential equations with the entire prehistory and a small parameter and takes into account continuous Wiener-type and discontinuous Poisson-type perturbations. It is proved that the sought-for control can be found as an optimal control of some auxiliary problem. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 181–186, May–June 2007.     

r-Algorithms and ellipsoids

Conclusion Transformation (6) smoothing thef(x) level lines explains the effectiveness ofr(α)-algorithms from visual geometrical considerations. It may be regarded as a satisfactory interpretation of space dilation in the direction of the difference of two successive subgradients. On the other hand, it preserves the gradient flavor of the method, in contrast to the classical ellipsoid method [11, 12], which is a successful interpretation of the subgradient method with space dilation in the direction of the subgradient. A sensible combination of ellipsoids of a special kind [5] with the ellipsoids ell(x₀,a, b, c) is quite capable of producing, on the basis of a one-dimensional space dilation operator, effective algorithms that solve a broader class of problems than convex programming problems, e.g., the problem to find saddle points of convex-concave functions, particular cases of the problem of solving variational inequalities, and also special classes of linear and nonlinear complementarity problems. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 113–134, January–February, 1996.     

State estimation and filtering in stochastic systems using adequate simplification

The method of order reduction in solving stochastic problems of state estimation and filtering is considered. The method presented concerns the case where mathematical models of objects being studied are defined by systems of nonstationary differential equations. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 98–102, September–October, 1999.     

A model of optimal control over a nonlinear multidimensional innovation diffusion process

A model of competitive innovation diffusion is considered. The model is based on the Lotka-Volterra system and an initial-boundary problem for a system of quasilinear parabolic equations. The maximum principle is proved for the problem of diffusion of two competitive innovations, and sufficient conditions of existence of optimum control are obtained for the system. A numerical algorithm is constructed for solving optimum control problems, and numerical results for a model example are presented. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 120–133, July–August 2008.     

Optimal control as a graphical model inference problem

We reformulate a class of non-linear stochastic optimal control problems introduced by Todorov (in Advances in Neural Information Processing Systems, vol. 19, pp. 1369–1376, 2007) as a Kullback-Leibler (KL) minimization problem. As a result, the optimal control computation reduces to an inference computation and approximate inference methods can be applied to efficiently compute approximate optimal controls. We show how this KL control theory contains the path integral control method as a special case. We provide an example of a block stacking task and a multi-agent cooperative game where we demonstrate how approximate inference can be successfully applied to instances that are too complex for exact computation. We discuss the relation of the KL control approach to other inference approaches to control.     

Convergence of a jump procedure in a semi-Markov environment in diffusion-approximation scheme

The sufficient convergence conditions are obtained for a jump stochastic approximation procedure in a semi-Markov environment in a diffusion approximation scheme with balance conditions for a singular perturbation of the regression function. To this end, a singular perturbation problem is solved for the asymptotic representation of the compensating operator of an augmented Markov renewal process. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 124–133, November–December 2007.