On Approximate Jumbled Pattern Matching in Strings

Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of a Parikh vector q in the text s requires finding a substring t of s with p(t)=q. This can be viewed as the task of finding a jumbled (permuted) version of a query pattern, hence the term Jumbled Pattern Matching. We present several algorithms for the approximate version of the problem: Given a string s and two Parikh vectors u,v (the query bounds), find all maximal occurrences in s of some Parikh vector q such that u≤q≤v. This definition encompasses several natural versions of approximate Parikh vector search. We present an algorithm solving this problem in sub-linear expected time using a wavelet tree of s, which can be computed in time O(n) in a preprocessing phase. We then discuss a Scrabble-like variation of the problem, in which a weight function on the letters of s is given and one has to find all occurrences in s of a substring t with maximum weight having Parikh vector p(t)≤v. For the case of a binary alphabet, we present an algorithm which solves the decision version of the Approximate Jumbled Pattern Matching problem in constant time, by indexing the string in subquadratic time.     

Double solutions of boundary value problems for 2mth-order differential equations and difference equations

A double fixed-point theorem is applied to obtain the existence of at least two positive solutions for the boundary value problem, (−1)^my^(2m)(t) = f(y(t)), t ϵ [0, 1], y⁽²ⁱ⁾(0) = y⁽²ⁱ⁺¹⁾(1) = 0, 0 ≤ i ≤ m−1. It is later applied to obtain the existence of at least two positive solutions for the analogous discrete boundary value problem, (−1)^mΔ^2mu(k) = g(u(k)), k ϵ {0, …, N}, Δ²ⁱu(0) = Δ²ⁱ⁺¹u(N + 1) = 0, 0 ⩽ m − 1.     

Fast Algorithms for the Density Finding Problem

We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a ₁,w ₁),(a ₂,w ₂),…,(a _n ,w _n ) of n ordered pairs (a _i ,w _i ) of numbers a _i and width w _i >0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i ^*,j ^*) over all O(n ²) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑ _r=i ^j w _r ≤u such that its density is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog ² m) time and O(n+mlog m) space, where and w _min=min  _r=1 ⁿ w _r . As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem. Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001.     

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.     

Mapping Between 2-D Meshes of the Same Size

1IntroductionInrece11tyears,n1a11yparallelalgoritlImshavebeendesignedtosolvedifferentproblemso1lvario1ls11etworktopologics.Bi11arytrees,meshesandhypercubesarethethreeimportal1tl1etworktop()logieswllicllhaterpcoivedintensivestlldy.WiththeadvanceofVLSI,manyllewl1etworkssuchasstargrapl1[1]havebeenorwiIlbeintroduced.Inor相似文献   

Periods in Extensions of Words

Let π(w) denote the minimum period of the word w,let w be a primitive word with period π(w) < |w|, and let z be a prefix of w. It is shown that if π(wz) = π(w), then |z| < π(w) − gcd (|w|, |z|). Detailed improvements of this result are also proven. Finally, we show that each primitive word w has a conjugate w′ = vu, where w = uv, such that π(w′) = |w′| and |u| < π(w). As a corollary we give a short proof of the fact that if u,v,w are words such that u ² is a prefix of v ², and v ² is a prefix of w ², and v is primitive, then |w| > 2|u|.     

Functional expansions for nonlinear discrete-time systems

Given an input-output map associated with a nonlinear discrete-time state equationx(t + 1) =f(x(t);u(t)) and a nonlinear outputy(t) =h(x(t)), we present a method for obtaining a “discrete Volterra series” representation of the outputy(t) in terms of the controlsu(0), ...,u(t − 1). The proof is based on Taylor-type expansions of the iterated composition of analytic functions. It allows us to make an explicit construction of each kernel, that is, each coefficient of the series expansion ofy(t) in powers of the controls. This is achieved by making use of successive directional derivatives associated with a family of vector fields which are deduced from the discrete state equations. We discuss the use of these vector fields for the analysis and control of nonlinear discrete-time systems. This work was carried out while D. Normand-Cyrot was working at the I.A.S.I. (from March to October 1984) and with the financial support of the Italian C.N.R. (Consiglio Nazionale delle Ricerche).     

Recursive identification for EIV ARMAX systems

The input u _k and output y _k of the multivariate ARMAX system A(z)y _k = B(z)u _k + C(z)w _k are observed with noises: u _k ^ob ≜ u _k + ε _k ^u and y _k ^ob ≜ y _k + ε _k ^y , where ε _k ^u and ε _k ^y denote the observation noises. Such kind of systems are called errors-in-variables (EIV) systems. In the paper, recursive algorithms based on observations are proposed for estimating coefficients of A(z), B(z), C(z), and the covariance matrix Rw of w _k without requiring higher than the second order statistics. The algorithms are convenient for computation and are proved to converge to the system coefficients under reasonable conditions. An illustrative example is provided, and the simulation results are shown to be consistent with the theoretical analysis.     

Generalized dilations and the stabilization of uncertain systems via measurement feedback

We study the problem of semiglobally stabilizing uncertain nonlinear system

Full-size image

, with (A,B) in Brunowski form. We prove that if p₁(z,u,t)u and p₂(z,u,t)u are of order greater than 1 and 0, respectively, with “generalized” dilation δ_l(z,u)=(l¹⁻ⁿz₁,…,l⁻¹z_n−1,z_n,lu) and uniformly with respect to t, where z_i is the ith component of z, then we can achieve semiglobal stabilization via arbitrarily bounded linear measurement feedback.     

Mixed Discontinuous Galerkin Finite Element Method for the Biharmonic Equation

In this paper, we first split the biharmonic equation Δ² u=f with nonhomogeneous essential boundary conditions into a system of two second order equations by introducing an auxiliary variable v=Δu and then apply an hp-mixed discontinuous Galerkin method to the resulting system. The unknown approximation v _h of v can easily be eliminated to reduce the discrete problem to a Schur complement system in u _h , which is an approximation of u. A direct approximation v _h of v can be obtained from the approximation u _h of u. Using piecewise polynomials of degree p≥3, a priori error estimates of u−u _h in the broken H ¹ norm as well as in L ² norm which are optimal in h and suboptimal in p are derived. Moreover, a priori error bound for v−v _h in L ² norm which is suboptimal in h and p is also discussed. When p=2, the preset method also converges, but with suboptimal convergence rate. Finally, numerical experiments are presented to illustrate the theoretical results. Supported by DST-DAAD (PPP-05) project.     

Filtering of some nonlinear diffusions satisfying the general Bene condition

Under some regularity assumptions and the following generalization of the well-known Bene condition [1]:

Full-size image

, where F(t,z) = g⁻²(t)∫f(t,z)dz, F_t, F_z, F_zz, are partial derivatives of F, we obtain explicit formulas for the unnormalized conditional density q_t(z, x) α Px_t ε dz| y_s, 0 st, where diffusion x_t on R¹ solves x₀ = x, dx_t = [β(t) + α(t)x_t + f(t, x_t] dt + g(t) dw₁, and observation y_t = ∫_o^th(s)x_s ds + ∫_o^t(s) dw_2t, with w = (w₁, w₂) a two-dimensional Wiener process.     

Oscillation criteria of certain nonlinear partial difference equations

This paper is concerned with the nonlinear partial difference equation with continuous variables

,where a, σ_i, τ_i are positive numbers, h_i(x, y, u) ε C(R⁺ × R⁺ × R, R), uh_i(x, y, u) > 0 for u ≠ 0, h_i is nondecreasing in u, i = 1, …, m. Some oscillation criteria of this equation are obtained.     

On input-output linearization of discrete-time nonlinear systems

We consider a nonlinear discrete-time system of the form Σ: x(t+1)=f(x(t), u(t)), y(t) =h(x(t)), where x ε R^N, u ε R^m, y ε R^q and f and h are analytic. Necessary and sufficient conditions for local input-output linearizability are given. We show that these conditions are also sufficient for a formal solution to the global input-output linearization problem. Finally, we show that zeros at infinity of ε can be obtained by the structure algorithm for locally input-output linearizable systems.     

Adaptive suboptimal control of a linear system with bounded disturbance

An adaptive suboptimal control of a linear discrete system with unknown parameters is proposed. An additive disturbance v_t acting on the system is supposed to be uniformly bounded. The criterion is sup_vtI(y^∞₁, u^∞₁), where y_t is the output, u_t is the control. The adaptive control law gives almost the same guaranteed value of the criterion as the optimal linear feedback does for a system with known parameters.     

Asymptotic behavior of nonoscillatory solutions of neutral difference equations

The authors consider the m^th-order neutral difference equation D_m(y(n) + p(n)y(n − k) + q(n)f(y(σ(n))) = e(n), where m ≥ 1, {p(n)}, {q(n)}, {e(n)}, and {a₁(n)}, {a₂(n)}, …, {a_m−1(n)} are real sequences, a_i(n) > 0 for i = 1,2,…, m−1, a_m(n) ≡ 1, D₀z(n) = y(n)+p(n)y(n − k), D_iz(n) = a_i(n)ΔD_i−1z(n) for i = 1,2, …, m, k is a positive integer, {σ(n)} → ∞ is a sequence of positive integers, and R → R is continuous with u f(u) > 0 for u ≠ 0. In the case where {q(n)} is allowed to oscillate, they obtain sufficient conditions for all bounded nonoscillatory solutions to converge to zero, and if {q(n)} is a nonnegative sequence, they establish sufficient conditions for all nonoscillatory solutions to converge to zero. Examples illustrating the results are included throughout the paper.     

Nonlinear eigenvalue problems for quasilinear systems

The paper deals with the existence of positive solutions for the quasilinear system (Φ(u'))' + λh(t)f(u) = 0,0 < t < 1 with the boundary condition u(0) = u(1) = 0. The vector-valued function Φ is defined by Φ(u) = (q(t)(p(t)u₁), …, q(t)(p(t)u_n)), where u = (u₁, …, u_n), andcovers the two important cases (u) = u and (u) = up > 1, h(t) = diag[h₁(t), …, h_n(t)] and f(u) = (f¹(u), …, fⁿ (u)). Assume that fⁱ and h_i are nonnegative continuous. For u = (u₁, …, u_n), let

, f₀ = maxf¹₀, …, fⁿ₀ and f_∞ = maxf¹_∞, …, fⁿ_∞. We prove that the boundary value problem has a positive solution, for certain finite intervals of λ, if one of f₀ and f_∞ is large enough and the other one is small enough. Our methods employ fixed-point theorem in a cone.     

Two point hermite approximations for the solution of linear initial value and boundary value problems

Application of an idea originally due to Ch. Hermite allows the derivation of an approximate formula for expressing the integral ∫xixi?1y(x)dx as a linear combination of y(xi?1), y(xi), and their derivatives y(v)(xi?1) up to order v = α and y(v)(xi) up to order v = β. In addition to this integro-differential form a purely differential form of the 2-point Hermite approximation will be derived. Both types will be denoted by Hαβ-approximation. It will be shown that the well-known Obreschkoff-formulas contain no new elements compared to the much older Hαβ-method.The Hαβ-approximation will be applied to the solution of systems of ordinary differential equations of the type y'(x) = M(x)y(x) + q(x), and both initial value and boundary value problems will be treated. Function values at intermediate points x? (xi?1, xi) are obtained by the use of an interpolation formula given in this paper.An advantage of the Hαβ-method is the fact that high orders of approximation (α, β) allow an increase in step size hi. This will be demonstrated by the results of several test calculations.     

A new unconditionally stable ADI compact scheme for the two-space-dimensional linear hyperbolic equation

We formulate a new alternating direction implicit compact scheme of O(τ²+h ⁴) for the linear hyperbolic equation u _tt +2α u _t +β² u=u _xx +u _yy +f(x, y, t), 0<x, y<1, 0<t≤T, subject to appropriate initial and Dirichlet boundary conditions, where α>0 and β≥0 are real numbers. In this article, we show the method is unconditionally stable by the Von Neumann method. At last, numerical demonstrations are given to illustrate our result.     

The asymptotic self-similar behavior for the quasilinear heat equation with nonlinear boundary condition

In this paper the quasilinear heat equation with the nonlinear boundary condition is studied. The blow-up rate and existence of a self-similar solution are obtained. It is proved that the rescaled function

v(y,t)=(T−t)^{1/(2p+α−2)}u((T−t)^{(p−1)/(2p+α−2)}y,t),