On estimation of the probability of absence of collisions of some random mappings

Let X and Y be finite sets and φ: (X,Y) →Y be a mapping. Consider a random mapping i → φ(x_i,y_i), where x_i are arbitrarily chosen from the set X, whereas (y_i) is a random sample from Y without replacement. A two-sided bound is derived for the probability of absence of collisions of this mapping. A case of mapping, defined as φ(x, y)=x+ y modulo n, is considered in particular. The results may be used in the selection of identification codes. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 132–137, January–February, 2000.     

On the Attainable Order of Collocation Methods for the Neutral Functional-Differential Equations with Proportional Delays

In this paper, we extend the recent results of H. Brunner in BIT (1997) for the DDE y′(t)= by(qt), y(0)=1 and the DVIE y(t)=1+∫₀ ^t by(qs)ds with proportional delay qt, 0<q≤1, to the neutral functional-differential equation (NFDE): and the delay Volterra integro-differential equation (DVIDE) : with proportional delays p _i t and q _i t, 0<p _i ,q _i ≤1 and complex numbers a,b _i and c _i . We analyze the attainable order of m-stage implicit (collocation-based) Runge-Kutta methods at the first mesh point t=h for the collocation solution v(t) of the NFDE and the `iterated collocation solution u _it (t)' of the DVIDE to the solution y(t), and investigate the existence of the collocation polynomials M _m (t) of v(th) or M^ _m (t) of u _it (th), t∈[0,1] such that the rational approximant v(h) or u _it (h) is the (m,m)-Padé approximant to y(h) and satisfies |v(h)−y(h)|=O(h ^{2 m +1}). If they exist, then we actually give the conditions of M _m (t) and M^ _m (t), respectively. Received September 17, 1998; revised September 30, 1999     

Autoregressive spectral analysis when observations are missing

A new missing data algorithm ARFIL gives good results in spectral estimation. The log likelihood of a multivariate Gaussian random variable can always be written as a sum of conditional log likelihoods. For a complete set of autoregressive AR(p) data the best predictor in the likelihood requires only p previous observations. If observations are missing, the best AR predictor in the likelihood will in general include all previous observations. Using only those observations that fall within a finite time interval will approximate this likelihood. The resulting non-linear estimation algorithm requires no user provided starting values. In various simulations, the spectral accuracy of robust maximum likelihood methods was much better than the accuracy of other spectral estimates for randomly missing data.     

Laplace transformations as the only degenerate Darboux transformations of first order

The paper is devoted to the Darboux transformations, an effective algorithm for finding analytical solutions of partial differential equations. It is proved that Wronskian-like formulas suggested by G. Darboux for the second-order linear operators on the plane describe all possible differential transformations with M of the form D _x + m(x, y) and D _y + m(x, y), except for the Laplace transformations.     

On a decidable generalized quantifier logic corresponding to a decidable fragment of first-order logic

Van Lambalgen (1990) proposed a translation from a language containing a generalized quantifierQ into a first-order language enriched with a family of predicatesR _i, for every arityi (or an infinitary predicateR) which takesQxg(x, y₁,..., y_n) to x(R(x, y₁,..., y₁) (x,y₁,...,y_n)) (y ₁,...,y_n are precisely the free variables ofQx). The logic ofQ (without ordinary quantifiers) corresponds therefore to the fragment of first-order logic which contains only specially restricted quantification. We prove that it is decidable using the method of analytic tableaux. Related results were obtained by Andréka and Németi (1994) using the methods of algebraic logic.     

Existence and efficient construction of fast Fourier transforms on supersolvable groups

The linear complexityL _K(A) of a matrixA over a fieldK is defined as the minimal number of additions, subtractions and scalar multiplications sufficient to evaluateA at a generic input vector. IfG is a finite group andK a field containing a primitive exp(G)-th root of unity,L _K(G):= min{L _K(A)|A a Fourier transform forKG} is called theK-linear complexity ofG. We show that every supersolvable groupG has amonomial Fourier Transform adapted to a chief series ofG. The proof is constructive and gives rise to an efficient algorithm with running timeO(|G|²log|G|). Moreover, we prove that these Fourier transforms are efficient to evaluate:L _K(G)8.5|G|log|G| for any supersolvable groupG andL _K(G)1.5|G|log|G| for any 2-groupG.     

An efficient solution to the subset‐sum problem on GPU

We present an algorithm to solve the subset‐sum problem (SSP) of capacity c and n items with weights w_i,1≤i≤n, spending O(n(m − w_min)/p) time and O(n + m − w_min) space in the Concurrent Read/Concurrent Write (CRCW) PRAM model with 1≤p≤m − w_min processors, where w_min is the lowest weight and , improving both upper‐bounds. Thus, when n≤c, it is possible to solve the SSP in O(n) time in parallel environments with low memory. We also show OpenMP and CUDA implementations of this algorithm and, on Graphics Processing Unit, we obtained better performance than the best sequential and parallel algorithms known so far. Copyright © 2015 John Wiley & Sons, Ltd.     

Asymptotic and oscillatory behavior of solutions of general nonlinear difference equations of second order

The asymptotic and oscillatory behavior of solutions of some general second-order nonlinear difference equations of the form

δ(a_nh(y_n+1)δy_n)+p_nδy_n+q_n+1f(y_σ(n+1))=0 nZ,

is studied. Oscillation criteria for their solutions, when “p_n” is of constant sign, are established. Results are also presented for the damped-forced equation

δ(a_nh(y_n+1)δy_n)+p_nδy_n+q_n+1f(y_σ(n+1))=e_n nZ.

Examples are inserted in the text for illustrative purposes.     

Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs

An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1 and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between x and y in G. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):vV(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ² for any simple graph with maximum degree Δ≥2. This paper considers the graph formed by the skew product and the converse skew product of two graphs with a new approach on the analysis of adjacency matrices of the graphs as in [W.C. Shiu, Z. Shao, K.K. Poon, D. Zhang, A new approach to the L(2,1)-labeling of some products of graphs, IEEE Trans. Circuits Syst. II: Express Briefs (to appear)] and improves the previous upper bounds significantly.     

A linearization procedure and a VDM/ECM algorithm for penalized and constrained nonparametric maximum likelihood estimation for mixture models

Suppose independent observations X_i, i=1,…,n are observed from a mixture model , where λ is a scalar and Q(λ) is a nondegenerate distribution with an unspecified form. We consider to estimate Q(λ) by nonparametric maximum likelihood (NPML) method under two scenarios: (1) the likelihood is penalized by a functional g(Q); and (2) Q is under a constraint g(Q)=g₀. We propose a simple and reliable algorithm termed VDM/ECM for Q-estimation when the likelihood is penalized by a linear functional. We show this algorithm can be applied to a more general situation where the penalty is not linear, but a function of linear functionals by a linearization procedure. The constrained NPMLE can be found by penalizing the quadratic distance |g(Q)-g₀|² under a large penalty factor γ>0 using this algorithm. The algorithm is illustrated with two real data sets.     

Orthonormal Basis Functions for Continuous-Time Systems and Lp Convergence

In this paper, model sets for linear-time-invariant continuous-time systems that are spanned by fixed pole orthonormal bases are investigated. These bases generalize the well-known Laguerre and two-parameter Kautz cases. It is shown that the obtained model sets are everywhere dense in the Hardy space H ₁(Π) under the same condition as previously derived by the authors for the denseness in the (Π is the open right half plane) Hardy spaces H _p(Π), 1<p<∞. As a further extension, the paper shows how orthonormal model sets, that are everywhere dense in H _p(Π), 1≤p<∞, and which have a prescribed asymptotic order, may be constructed. Finally, it is established that the Fourier series formed by orthonormal basis functions converge in all spaces H _p(Π) and (D is the open unit disk) H _p(D), 1<p<∞. The results in this paper have application in system identification, model reduction, and control system synthesis. Date received: June 16, 1998. Date revised February 4, 1999.     

A new universal approximation result for fuzzy systems,which reflects CNF DNF duality

There are two main fuzzy system methodologies for translating expert rules into a logical formula: In Mamdani's methodology, we get a DNF formula (disjunction of conjunctions), and in a methodology which uses logical implications, we get, in effect, a CNF formula (conjunction of disjunctions). For both methodologies, universal approximation results have been proven which produce, for each approximated function f(x), two different approximating relations R_DNF(x, y) and R_CNF(x, y). Since, in fuzzy logic, there is a known relation F_CNF(x) ≤ F_DNF(x) between CNF and DNF forms of a propositional formula F, it is reasonable to expect that we would be able to prove the existence of approximations for which a similar relation R_CNF(x, y) ≤ R_DNF(x, y) holds. Such existence is proved in our paper. © 2002 Wiley Periodicals, Inc.     

Feedback solution of a class of optimal bilinear control problems

Fuller's 1985 results on a class of optimal control problems for a double integrator system facilitate the solution of the following class (parametrized by μ ≥ 1) of optimal bilinear control problems: minimize ∫₀ ^∞ |y(t)|^μ dt subject to ÿ = yv with prescribed initial condition and control constraint |v(t)| ≤ 1.     

On the Weighted Mean of a Pair of Strings

String matching and string edit distance are fundamental concepts in structural pattern recognition. In this paper, the weighted mean of a pair of strings is introduced. Given two strings, x and y, where d(x, y) is the edit distance of x and y, the weighted mean of x and y is a string z that has edit distances d(x, z) and d(z, y)to x and y, respectively, such that d(x, z) _ d(z, y) = d(x, y). We’ll show formal properties of the weighted mean, describe a procedure for its computation, and give practical examples. Received: 26 October 2000, Received in revised form: 27 April 2001, Accepted: 20 July 2001     

New explicit filters and smoothers for diffusions with nonlinear drift and measurements

The optimal least-squares filtering of a diffusion x(t) from its noisy measurements {y(τ); 0 τ t} is given by the conditional mean E[x(t)|y(τ); 0 τ t]. When x(t) satisfies the stochastic diffusion equation dx(t) = f(x(t)) dt + dw(t) and y(t) = ∫₀^tx(s) ds + b(t), where f(·) is a global solution of the Riccati equation /xf(x) + f(x)² = f(x)² = αx² + βx + γ, for some , and w(·), b(·) are independent Brownian motions, Benes gave an explicit formula for computing the conditional mean. This paper extends Benes results to measurements y(t) = ∫₀^tx(s) ds + ∫₀^t dx(s) + b(t) (and its multidimensional version) without imposing additional conditions on f(·). Analogous results are also derived for the optimal least-squares smoothed estimate E[x(s)|y(τ); 0 τ t], s < t. The methodology relies on Girsanov's measure transformations, gauge transformations, function space integrations, Lie algebras, and the Duncan-Mortensen-Zakai equation.     

The improved split-step backward Euler method for stochastic differential delay equations

A new, improved split-step backward Euler method is introduced and analysed for stochastic differential delay equations (SDDEs) with generic variable delay. The method is proved to be convergent in the mean-square sense under conditions (Assumption 3.1) that the diffusion coefficient g(x, y) is globally Lipschitz in both x and y, but the drift coefficient f(x, y) satisfies the one-sided Lipschitz condition in x and globally Lipschitz in y. Further, the exponential mean-square stability of the proposed method is investigated for SDDEs that have a negative one-sided Lipschitz constant. Our results show that the method has the unconditional stability property, in the sense, that it can well reproduce stability of the underlying system, without any restrictions on stepsize h. Numerical experiments and comparisons with existing methods for SDDEs illustrate the computational efficiency of our method.     

Small deviations for two classes of Gaussian stationary processes and <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript>-functionals, 0 < <Emphasis Type="Italic">p</Emphasis> ≤ ∞

Let w(t) be a standard Wiener process, w(0) = 0, and let η _a (t) = w(t + a) − w(t), t ≥ 0, be increments of the Wiener process, a > 0. Let Z _a (t), t ∈ [0, 2a], be a zeromean Gaussian stationary a.s. continuous process with a covariance function of the form E Z _a (t)Z _a (s) = 1/2[a − |t − s|], t, s ∈ [0, 2a]. For 0 < p < ∞, we prove results on sharp asymptotics as ɛ → 0 of the probabilities

Spectral factorization of time-varying covariance functions: The singular case

If a known linear system is excited by Gaussian white noise, the calculation of the output covariance of the system is relatively straightforward. This paper considers the harder converse problem, that of passing from a known covariance to a system which will generate it. The problem is solved for covariancesR _y (t, ) with |R _y (t, t)| < for allt and such that they-process is Gauss-Markov, i.e., it may be obtained as the output of a linear finite-dimensional system excited by white noise.Work supported by Australian Research Grants Committee; MS submitted June 1968.     

Stability analysis of Euler‐Bernoulli beam with input delay in the boundary control

In this paper, we investigate an Euler‐Bernoulli system with input delay in the boundary control. Suppose that there is no delay in observation, y(t), of the system, and a partial input delay in the boundary control. The collocated boundary feedback control law u(t) = αy(t) + βy(t ? τ) is applied to obtain the closed loop system. By spectral analysis and Lyapunov method, we show that: when α>|β|, the closed loop system is exponentially stable for any τ>0; when α<|β|, the system is unstable for any τ>0; when α = |β|, the system is asymptotically stable for almost all τ>0. Finally, we provide numerical simulations to show the spectral distribution for different values of α and β. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society