Models with conjugation conditions and high-accuracy methods of their discretization

New classes of problems with discontinuous solutions are considered. Corresponding generalized problems are obtained. Increased-accuracy computational schemes for their discretization are proposed. Numerical schemes are proposed with asymptotic accuracy not worse than that of similar schemes for problems with smooth solutions. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 110–131, January–February, 2000.     

Analysis of mathematical models and methods of solving combinatorial optimization problems on game-type permutations

The paper is concerned with an optimization problem on game-type permutations, where one or both players have combinatorial constraints on their strategies. A mathematical model of such problems is constructed and analyzed. A modified graphical method is proposed to solve (2xn)-and (mx2)-dimensional problems. High-dimensional problems are reduced to linear programming and combinatorial optimization problems. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 103–114, November–December 2007.     

How to make constrained fuzzy arithmetic efficient

 In the standard fuzzy arithmetic, the vagueness of fuzzy quantities always increases. G. J. Klir [2, 3] suggests an alternative – the constrained fuzzy arithmetic – which reduces this effect. On the other hand, it significantly increases the complexity of computations in comparison to the classical calculus of fuzzy quantities. So far, little attention was paid to the problems of implementation of the constrained fuzzy arithmetic, especially to its computational efficiency. We point out the related problems and outline the ways of their solution. We suggest to decompose the whole expression, classify all its subexpressions with respect to their individual computational complexity and precompute the corresponding subresults according to this classification.     

Problems of creating intelligent autonomous robotic underwater vehicles and their application

Basic scientific and applied tasks to be accomplished by autonomous robotic underwater vehicles are considered, and distinctive features of their control system are analyzed. Some unsolved fundamental problems in this subject are formulated. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 100–110, September–October 2007.     

Quantum model of computations: Underlying principles and achievements

A quantum Turing machine is considered. A review of basic methodological principles and achievements in the field of quantum computations is given. Some problems of construction of correct quantum computations and their complexity are considered. The result of P. Shor concerning the solution of the problems of taking discrete logarithms in polynomial time relative to the length of numbers is considered in detail. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 58–76, January–February, 2000.     

Age differences rendezvousing: reminders for side-stepping

This paper reports a diary study of the use of mobile telephones for rendezvousing by young adults (aged 18–30) and mature adults (aged 31–45) in the UK. A number of age differences were found. Specifically, 31–45s more frequently: (1) attributed problems rendezvousing to the overrunning of previous activities, and to the spontaneous performance of additional tasks (‘side-stepping’); (2) reported that ‘problem’ rendezvous resulted in unnecessary sacrifices; and (3) changed plans for the rendezvous. These differences arose, because additional family commitments encouraged 31–45s to pack their daily programme of activities more tightly than 18–30s. Mobile phones might better target 31–45s, if they, for example, enhanced To Do Lists with context-sensitive reminders, in the first instance, reminders triggered by location (GSM network cellID) and logging off from PCs.

---

     

On the status and prospects of systems analysis methods in ukraine

The paper deals with the role and place of systems analysis methods in the solution of complex problems in various spheres of human activity in Ukraine. The social and socio-economic prerequisites for development of theory and applied methods are being considered. The main characteristics of the problems to which these methods are applied are formulated. The hierarchy of problems and methods used for solution of complex problems based on systems analysis methods is presented, and the main spheres of their application in Ukraine are presented. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 101–109, January–February, 2000.     

On measuring and profiling catastrophic risks

An approach to decision-making under catastrophic risks based on risk profiling is proposed. The approach assumes, for some selected catastrophic scenarios, to simulate their consequences (damage) as functions of control parameters and to impose expert constraints on acceptable levels of relative losses in such scenarios. The approach is illustrated by a number of one-stage decision-making problems reduced to mixed linear-programming problems. The study was sponsored by the Ukrainian Center of Science and Technology, Project G3127. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 80–94, November–December 2006.     

Stabilization by Local Projection for Convection–Diffusion and Incompressible Flow Problems

We give a survey on recent developments of stabilization methods based on local projection type. The considered class of problems covers scalar convection–diffusion equations, the Stokes problem and the linearized Navier–Stokes equations. A new link of local projection to the streamline diffusion method is shown. Numerical tests for different type of boundary layers arising in convection–diffusion problems illustrate the stabilizing properties of the method.     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

A shared workspace to support man–machine reasoning: application to cooperative distant diagnosis

This paper focuses on man–machine cooperation problems. In particular, it deals with those problems that occur when both human and machine have to achieve a shared reasoning activity. It puts forward a man–machine approach that is dedicated to technical diagnosis problem solving. Coordination of human and automated reasoning is key to solving this problem, since efficiency depends on both sharing and interpreting exchanged data. A shared workspace is proposed to support both machines and their human operators. This workspace is kept as close as possible to human representations in order to reduce cooperation costs. The paper describes those coordination mechanisms that are able to support such a cooperative activity using a shared workspace. In order to assess the costs and benefits of such cooperation, these mechanisms are applied to a complex industrial problem: diagnosis and troubleshooting in a phone network. The results show the full impact of cooperation on human–machine reasoning.     

Fokker–Planck approximation of the master equation in molecular biology

The master equation of chemical reactions is solved by first approximating it by the Fokker–Planck equation. Then this equation is discretized in the state space and time by a finite volume method. The difference between the solution of the master equation and the discretized Fokker–Planck equation is analyzed. The solution of the Fokker–Planck equation is compared to the solution of the master equation obtained with Gillespie’s Stochastic Simulation Algorithm (SSA) for problems of interest in the regulation of cell processes. The time dependent and steady state solutions are computed and for equal accuracy in the solutions, the Fokker–Planck approach is more efficient than SSA for low dimensional problems and high accuracy.     

Morphological mismatches in machine translation

This paper addresses one of the least studied, although very important, problems of machine translation—the problem of morphological mismatches between languages and their handling during transfer. The level at which we assume transfer to be carried out is the Deep-Syntactic Structure (DSyntS) as proposed in the Meaning-Text Theory. DSyntS is abstract enough to avoid all types of surface morphological divergences. For the remaining ‘genuine’ divergences between grammatical significations, we propose a morphological transfer model. To illustrate this model, we apply it to the transfer of grammemes of definiteness and aspect for the language pair Russian–German and German–Russian, respectively.     

Means of supporting the solution of differential equations in problem of supply-and-demand macroanalysis

This paper deals with models of demand-supply problems. A scheme of virtually organized computer support of the solution of such problems is discussed. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 174–183, July–August, 1999.     

Phase Portrait Modeling of a Nonlinear System with a Dynamic Fuzzy Network

Fuzzy logic and neural networks are two important technologies for modeling and control of dynamical systems and have been constrained by the non-dynamical nature of their some popular architectures. There exist problems such as large rule bases (i.e., curse of dimensionality), long training times, the need to determine buffer lengths. This article proposes to overcome these major problems in phase portrait modeling of a nonlinear system with a dynamic fuzzy network (DFN) with unconstrained connectivity and with dynamic fuzzy processing units called “feurons”. Nonlinear physical system properties can be encapsulated by DFN. As an example, DFN has been used as the modeler for some nonlinear physical system such as chaotic, limit cycle, oscillator. The minimization of an integral quadratic performance index subject to dynamic equality constraints is considered for a phase portrait modeling application. For gradient computation adjoint sensitivity method has been used. Its computational complexity is significantly less than direct sensitivity method, but it requires a backward integration capability. We used first and approximate second order gradient-based methods including Broyden–Fletcher–Golfarb–Shanno algorithm to update the parameters of the dynamic fuzzy networks yielding faster rate of convergence     

Nonlinear automata over a finite ring

The properties of the class of information-lossless automata represented by recurrent relations over a finite ring are investigated. For these automata, the structure of classes of equivalent states is investigated, problems of parametric identification and identification of the initial state are solved, and the variation in the behavior of such automata as a result of variation of their parameters or initial states is characterized. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 29–42, November–December 2006.     

Problems with conjugation conditions and their high-accuracy computational discretization algorithms

New classes of problems with discontinuous solutions are considered. The corresponding generalized problems are obtained. Numerical schemes, which are as asymptotically accurate as similar schemes for problems with smooth solutions, are proposed for the new classes of problems. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 100–124, November–December, 1999.     

Methods of searching for guaranteeing and optimistic solutions to integer optimization problems under uncertainty

The paper studies complex integer optimization problems with inexact coefficients of the linear objective function and convex quadratic constraint functions. Exact and approximate decomposition methods are developed and proved to search for guaranteeing and optimistic solutions to such problems. The methods are based on approximation of initial problems by problems of a simpler structure. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 103–114, January–February 2007.     

Hybrid Extensional Prototype Compositionality

It has been argued that prototypes cannot compose, and that for this reason concepts cannot be prototypes (Osherson and Smith in Cognition 9:35–58, 1981; Fodor and Lepore in Cognition 58:253–270, 1996; Connolly et al. in Cognition 103:1–22, 2007). In this paper I examine the intensional and extensional approaches to prototype compositionality, arguing that neither succeeds in their present formulations. I then propose a hybrid extensional theory of prototype compositionality, according to which the extension of a complex concept is determined as a function of what triggers its constituent prototypes. I argue that the theory escapes the problems traditionally raised against extensional theories of compositionality.     

Implementing Radau IIA Methods for Stiff Delay Differential Equations

This article discusses the numerical solution of a general class of delay differential equations, including stiff problems, differential-algebraic delay equations, and neutral problems. The delays can be state dependent, and they are allowed to become small and vanish during the integration. Difficulties encountered in the implementation of implicit Runge–Kutta methods are explained, and it is shown how they can be overcome. The performance of the resulting code – RADAR5 – is illustrated on several examples, and it is compared to existing programs. Received October 12, 2000