Trial and Error

A pac-learning algorithm is -space bounded, if it stores at most examples from the sample at any time. We characterize the -space learnable concept classes. For this purpose we introduce the compression parameter of a concept class and design our Trial and Error Learning Algorithm. We show : is -space learnable if and only if the compression parameter of is at most . This learning algorithm does not produce a hypothesis consistent with the whole sample as previous approaches e.g. by Floyd, who presents consistent space bounded learning algorithms, but has to restrict herself to very special concept classes. On the other hand our algorithm needs large samples; the compression parameter appears as exponent in the sample size. We present several examples of polynomial time space bounded learnable concept classes: – all intersection closed concept classes with finite VC–dimension. – convex -gons in . – halfspaces in . – unions of triangles in . We further relate the compression parameter to the VC–dimension, and discuss variants of this parameter. Received May 24, 1994 / July 4, 1995     

Stability condition for m/d/l retrial queuing system with a limited waiting time

A stability condition is derived for a queueing system with a Poisson input with parameter λ and constant service time τ. If the virtual waiting time is less than a constant a, then the demand can be serviced; otherwise, it is repeated in exponentially distributed time or is lost with a probability q >- 0. Translated from Kibemetika i Sisternnyi Anaiii. No. 2, pp. 184–186, March–April, 2000.     

Analysis of systems of singular ordinary differential equations

Systems of ordinary differential equations with a small parameter at the derivative and specific features of the construction of their periodic solution are considered. Sufficient conditions of existence and uniqueness of the periodic solution are presented. An iterative procedure of construction of the steady-state solution of a system of differential equations with a small parameter at the derivative is proposed. This procedure is reduced to the solution of a system of nonlinear algebraic equations and does not involve the integration of the system of differential equations. Problems of numerical calculation of the solution are considered based on the procedure proposed. Some sources of its divergence are found, and the sufficient conditions of its convergence are obtained. The results of numerical experiments are presented and compared with theoretical ones. Translated from Kibemetika i Sistemnyi Analiz, No. 5, pp. 103–110, September–October, 1999.     

Slowly rotating wormholes: the first-order approximation

We discuss a solution describing a rotating wormhole in general relativity with a scalar field source having negative kinetic energy. To solve the problem, we use the assumption of slow rotation. The role of a small dimensionless parameter is played the ratio of the linear velocity of rotation of the wormhole throat and the velocity of light. The rotating wormhole solution is constructed in the first-order approximation with respect to the small parameter. We analyze the solution obtained and study test particle motion and light propagation in the spacetime of a rotating wormhole. Talk given at the Russian School-Seminar on Modern Problems of Gravitation and Cosmology, Kazan-Yal’chik, 10–15 September 2007.     

Solution of inverse boundary-value problems for multicomponent parabolic distributed systems

Computational algorithms implementing gradient methods based on solution of direct and adjoint problems in weak formulations are proposed for a number of complex-valued inverse problems of parameter renewal in multicomponent parabolic distributed systems. This approach makes it unnecessary to construct Lagrangian functionals explicitly and to use Green’s functions. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 49–73, July–August 2007.     

Stability radius of an efficient solution of a vector problem of integer linear programming in the Gölder metric

A vector (multicriterion) problem of integer linear programming is considered on a finite set of feasible solutions. A metric l_p, 1 ≤ p ≤ ∞, is defined on the parameter space of the problem. A formula of the maximum permissible level of perturbations is obtained for the parameters that preserve the efficiency (Pareto optimality) of a given solution. Necessary and sufficient conditions of two types of stability of the problem are obtained as corollaries. This work has been carried out with financial support from the Belgosuniversity within the framework of the Intercollegiate Program “Fundamental and Applied Investigations” (project No. 492/28). __________ Translated from Kibernetika I Sistemnyi Analiz, No. 4, pp. 175–181, July–August 2006.     

Using linear models in optimizing parameters of time-triggered protocols

A mechanism of synchronization of components of distributed systems in which communications are based on a common time schedule for all system components is illustrated by examples of simple Time-Triggered Protocols. For parametric linear models of synchronization, the optimization problem is considered for a parameter that should exclude the overlapping of messages in communication channels. The results of using numeric methods for estimation of the optimal value of this parameter are described. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 24–32, May–June 2006.     

Short term memory in recurrent networks of spiking neurons

We present in this paper a general model of recurrent networks of spiking neurons, composed of several populations, and whose interaction pattern is set with a random draw. We use for simplicity discrete time neuron updating, and the emitted spikes are transmitted through randomly delayed lines. In excitatory-inhibitory networks, we show that inhomogeneous delays may favour synchronization provided that the inhibitory delays distribution is significantly stronger than the excitatory one. In that case, slow waves of synchronous activity appear (this synchronous activity is stronger in inhibitory population). This synchrony allows for a fast ada ptivity of the network to various input stimuli. In networks observing the constraint of short range excitation and long range inhibition, we show that under some parameter settings, this model displays properties of –1– dynamic retention –2– input normalization –3– target tracking. Those properties are of interest for modelling biological topologically organized structures, and for robotic applications taking place in noisy environments where targets vary in size, speed and duration. This revised version was published online in June 2006 with corrections to the Cover Date.     

A new mutation operator for evolutionary airfoil design

A new mutation operator, ℳ _ijn , capable of operating on a set of adjacent bits in one single step, is introduced. Its features are examined and compared against those of the classical bit–flip mutation. A simple Evolutionary Algorithm, ℳ–EA, based only on selection and ℳ _ijn , is described. This algorithm is used for the solution of an industrial problem, the Inverse Airfoil Design optimization, characterized by high search time to achieve satisfying solutions, and its performance is compared against that offered by a classical binary Genetic Algorithm. The experiments show for our algorithm a noticeable reduction in the time needed to reach a solution of acceptable quality, thus they prove the effectiveness of the proposed operator and its superiority to GAs for the problem at hand.     

The asymptotic properties of estimates of the parameters of nonlinear time series

Asymptotic properties of nonlinear time series parameter estimators constructed on trajectories of stochastic systems under stationary and transient conditions are studied with the use of the least-squares method. The investigation method is based on the study of asymptotic properties of extremal sets of random functions. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 62–72, March–April, 2000     

Algebraic Fractional-Step Schemes for Time-Dependent Incompressible Navier–Stokes Equations

The numerical investigation of a recent family of algebraic fractional-step methods (the so called Yosida methods) for the solution of the incompressible time-dependent Navier–Stokes equations is presented. A comparison with the Karniadakis–Israeli–Orszag method Karniadakis et al. (1991, J. Comput. Phys. 97, 414–443) is carried out. The high accuracy in time of these schemes well combines with the high accuracy in space of spectral methods.     

Computer-based techniques for solving problems of applied and computational mathematics with given quality characteristics

The paper is concerned with computer-based techniques for the choice and development of computational resources and their efficient use to find an approximate solution with a given accuracy in a limited processor time. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 33–41, September–October 2006.     

Estimation of some parameters of pseudo-Gaussian random processes

An estimate and a confidence interval are constructed for the Baxter parameter of a pseudo-Gaussian random process with the help of the Levi-Baxter-Gladyshev theorem for weighted variations. An essential advantage of the proposed estimation method is that it estimates a process not from its realizations but from its observations at discrete moments of time. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 76–83, May–June 2006.     

Transition Dynamics in Endogenous Recombinant Growth Models by Means of Projection Methods

This study provides a step further in the computation of the transition path of a continuous time endogenous growth model discussed by Privileggi (Nonlinear dynamics in economics, finance and social sciences: essays in honour of John Barkley Rosser Jr., Springer, Berlin, Heidelberg, pp. 251–278, 2010)—based on the setting first introduced by Tsur and Zemel (J Econ Dyn Control 31:3459–3477, 2007)—in which knowledge evolves according to the Weitzman (Q J Econ 113:331–360, 1998) recombinant process. A projection method, based on the least squares of the residual function corresponding to the ODE defining the optimal policy of the ‘detrended’ model, allows for the numeric approximation of such policy for a positive Lebesgue measure range of values of the efficiency parameter characterizing the probability function of the recombinant process. Although the projection method’s performance rapidly degenerates as one departs from a benchmark value for the efficiency parameter, we are able to numerically compute time-path trajectories which are sufficiently regular to allow for sensitivity analysis under changes in parameters’ values.     

Multichannel image segmentation using adaptive finite elements

We present an adaptive finite element algorithm for segmentation with denoising of multichannel images in two dimensions, of which an extension to three dimensional images is straight forward. It is based on a level set formulation of the Mumford–Shah approach proposed by Chan and Vese in (JVCIR 11:130–141,(2000); IEEE Trans Image Proces 10(2):266–277, (2001); Int J Comp Vis 50(3):271–293, (2002)) In case of a minimal partition problem an exact solution is given and convergence of the discrete solution towards this solution is numerically verified.     

Higher-Order Gauss–Lobatto Integration for Non-Linear Hyperbolic Equations

Least-squares spectral elements are capable of solving non-linear hyperbolic equations, in which discontinuities develop in finite time. In recent publications [De Maerschalck, B., 2003, http://www.aero.lr.tudelft.nl/∼bart; De Maerschalck, B., and Gerritsma, M. I., 2003, AIAA; De Maerschalck, B., and Gerritsma, M. I., 2005, Num. Algorithms, 38(1–3); 173–196], it was noted that the ability to obtain the correct solution depends on the type of linearization, Picard’s method or Newton linearization. In addition, severe under-relaxation was necessary to reach a converged solution. In this paper the use of higher-order Gauss–Lobatto integration will be addressed. When a sufficiently fine GL-grid is used to approximate the integrals involved, the discrepancies between the various linearization methods are considerably reduced and under-relaxation is no longer necessary     

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.     

Accuracy of Approximation of a Solution to an Abstract Cauchy Problem

A constructive image of the solution to a homogeneous Cauchy problem in a Banach space with a densely specified linear closed logarithmically-sector operator is investigated. The uniform accuracy of estimation of an approximate solution in t ≥ 0 is proved. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 145–152, May–June 2005.     

Enhanced Coercivity for Pure Advection and Advection–Diffusion Problems

We present a common framework in which to set advection problems or advection–diffusion problems in the advection dominated regime, prior to any discretization. It allows one to obtain, in an easy way via enhanced coercivity, a bound on the advection derivative of the solution in a fractional norm of order −1/2. The same bound trivially applies to any Galerkin approximate solution, yielding a stability estimate which is uniform with respect to the diffusion parameter. The proposed formulation is discussed within Fourier methods and multilevel (wavelet) methods, for both steady and unsteady problems.Dedicated to David Gottlieb on the occasion of his 60th Birthday.