Pattern Matching with Swaps

Let a text string T of n symbols and a pattern string P of m symbols from alphabet Σ be given. A swapped version T′ of T is a length n string derived from T by a series of local swaps (i.e., t′_ℓ ← t_ℓ + 1 and t′_ℓ + 1 ← t_ℓ), where each element can participate in no more than one swap. The pattern matching with swaps problem is that of finding all locations i for which there exists a swapped version T′ of T with an exact matching of P in location i of T′. It has been an open problem whether swapped matching can be done in less than O(nm) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time o(nm). We present an algorithm whose time complexity is O(nm^1/3 log m log σ) for a general alphabet Σ, where σ = min(m,Σ).     

On nonautonomous linear systems of differential and difference equations with -symmetric coefficient matrices

Let denote the set of continuous n×n matrices on an interval . We say that is a nontrivial k-involution if where ζ=e^-2πi/k, d₀+d₁++d_k-1=n, and with . We say that is R-symmetric if R(t)A(t)R^-1(t)=A(t), , and we show that if A is R-symmetric then solving x^′=A(t)x or x^′=A(t)x+f(t) reduces to solving k independent d_ℓ×d_ℓ systems, 0ℓk-1. We consider the asymptotic behavior of the solutions in the case where . Finally, we sketch analogous results for linear systems of difference equations.     

On the Common Substring Alignment Problem

The Common Substring Alignment Problem is defined as follows: Given a set of one or more strings S₁, S₂ … S_c and a target string T, Y is a common substring of all strings S_i, that is, S_i = B_iYF_i. The goal is to compute the similarity of all strings S_i with T, without computing the part of Y again and again. Using the classical dynamic programming tables, each appearance of Y in a source string would require the computation of all the values in a dynamic programming table of size O(nℓ) where ℓ is the size of Y. Here we describe an algorithm which is composed of an encoding stage and an alignment stage. During the first stage, a data structure is constructed which encodes the comparison of Y with T. Then, during the alignment stage, for each comparison of a source S_i with T, the pre-compiled data structure is used to speed up the part of Y. We show how to reduce the O(nℓ) alignment work, for each appearance of the common substring Y in a source string, to O(n)-at the cost of O(nℓ) encoding work, which is executed only once.     

Contractivity properties of Ornstein-Uhlenbeck semigroup for general commutation relations

We study a certain class of von Neumann algebras generated by selfadjoint elements ω_i=a_i+a_i⁺, where a_i, a_i⁺ satisfy the general commutation relations:We assume that operator T for which the constants are matrix coefficients satisfies the braid relation. Such algebras were investigated in [BSp] and [K] where the positivity of the Fock representation and factoriality were shown. In this paper we prove that T-Ornstein-Uhlenbeck semigroup U_t=Γ_T(e^−t), t>0 arising from the second quantization procedure is hyper- and ultracontractive. The optimal bounds for hypercontractivity are also discussed.This paper was partially supported by KBN grant no 2P03A00732 and also by RTN grant HPRN-CT-2002-00279.     

Privileged users in zero-error transmission over a noisy channel

The k-th power of a graph G is the graph whose vertex set is V(G) ^k , where two distinct k-tuples are adjacent iff they are equal or adjacent in G in each coordinate. The Shannon capacity of G, c(G), is lim _k→∞ α(G ^k )^1/k , where α(G) denotes the independence number of G. When G is the characteristic graph of a channel C, c(G) measures the effective alphabet size of C in a zero-error protocol. A sum of channels, C = Σ _i C _i , describes a setting when there are t ≥ 2 senders, each with his own channel C _i , and each letter in a word can be selected from any of the channels. This corresponds to a disjoint union of the characteristic graphs, G = Σ _i G _i . It is well known that c(G) ≥ Σ _i c(G _i ), and in [1] it is shown that in fact c(G) can be larger than any fixed power of the above sum. We extend the ideas of [1] and show that for every F, a family of subsets of [t], it is possible to assign a channel C _i to each sender i ∈ [t], such that the capacity of a group of senders X ⊂ [t] is high iff X contains some F ∈ F. This corresponds to a case where only privileged subsets of senders are allowed to transmit in a high rate. For instance, as an analogue to secret sharing, it is possible to ensure that whenever at least k senders combine their channels, they obtain a high capacity, however every group of k − 1 senders has a low capacity (and yet is not totally denied of service). In the process, we obtain an explicit Ramsey construction of an edge-coloring of the complete graph on n vertices by t colors, where every induced subgraph on exp vertices contains all t colors. Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research partially supported by a Charles Clore Foundation Fellowship.     

Recursive constructions for skew resolutions in affine geometries

A resolutionR inAG(n, q) is defined to be a partition of the lines into classesR ₁,R ₂, ...,R _t (t=(q ⁿ –1)/(q–1)) such that each point of the geometry is incident with precisely one line of each classR _l , 1it. Of course, the equivalence relation of parallelism defines a resolution in any affine geometry. A resolutionR is said to be a skew resolution provided noR _i , 1it, contains two parallel lines. Skew resolutions are useful for producing packings of lines in projective spaces and doubly resolvable block designs. Skew resolutions are known to exist inAG(n, q),n=2^t–1,i2,q a prime power. The entire spectrum is unknown. In this paper, we give two recursive constructions for skew resolutions. These constructions produce skew resolutions inAG(n, q) for infinietly many new values ofn.     

Permanence and global stability in a Lotka-Volterra predator-prey system with delays

Consider the permanence and global asymptotic stability of models governed by the following Lotka-Volterra-type system:

, with initial conditions

x_i(t) = φ_i(t) ≥ o, t ≤ t₀, and φ_i(t₀) > 0. 1 ≤ i ≤n

. We define x₀(t) = x_n+1(t)≡0 and suppose that φ_i(t), 1 ≤ i ≤ n, are bounded continuous functions on [t₀, + ∞) and γ_i, α_i, c_i > 0,γ_i,j ≥ 0, for all relevant i,j.Extending a technique of Saito, Hara and Ma[1] for n = 2 to the above system for n ≥ 2, we offer sufficient conditions for permanence and global asymptotic stability of the solutions which improve the well-known result of Gopalsamy.     

On Approximate ℓ 1 Systems in Banach Spaces

Let X be a real Banach space and let (f(n)) be a positive nondecreasing sequence. We consider systems of unit vectors (x_i)^∞_i=1 in X which satisfy ∑_iA±x_i|A|−f(|A|), for all finite A and for all choices of signs. We identify the spaces which contain such systems for bounded (f(n)) and for all unbounded (f(n)). For arbitrary unbounded (f(n)), we give examples of systems for which [x_i] is H.I., and we exhibit systems in all isomorphs of ℓ₁ which are not equivalent to the unit vector basis of ℓ₁. We also prove that certain lacunary Haar systems in L₁ are quasi-greedy basic sequences.     

Parameterized matching with mismatches

The problem of approximate parameterized string searching consists of finding, for a given text t=t₁t₂…t_n and pattern p=p₁p₂…p_m over respective alphabets Σ_t and Σ_p, the injection π_i from Σ_p to Σ_t maximizing the number of matches between π_i(p) and t_it_i+1…t_i+m−1 (i=1,2,…,n−m+1). We examine the special case where both strings are run-length encoded, and further restrict to the case where one of the alphabets is binary. For this case, we give a construction working in time O(n+(r_p×r_t)α(r_t)log(r_t)), where r_p and r_t denote the number of runs in the corresponding encodings for y and x, respectively, and α is the inverse of the Ackermann's function.     

ON THE UNIFORM CONSISTENCY OF THEKAPLAN-MEIER ESTIMATOR UNDER HEAVY CENSORING

Let X,i.i.d. and Y1i. i.d. be two sequences of random variables with unknown distribution functions F(x) and G(y) respectively. X, are censored by Y1. In this paper we study the uniform consistency of the Kaplan-Meier estimator under the case ey=sup(t:F(t)＜1)＞to=sup(t2G(t)＜1) The sufficient condition is discussed.     

Properties of Hida processes on . 2. Prediction and interpolation problems for processes on

If E is an ordered set, we study the processes Y_t, t E, for which the vectorial spaces _t generated by all the conditional expectations E(Y_sβ _t) for s ≥ t have finite dimensions d(t) ≤ N. ( _t is some convenient filtration.) We first develop a geometrical approach in the general situation and give a “Goursat's representation” Y_t = Σf_i(t)M_i(t), where the M_i(t) are martingales. We then restrict us to the cases E = or E = ² and give representations of the processes by the mean of stochastic integrals of “Goursat's kernels.” The special case when Y_t is the solution of a differential equation is considered.     

The concentration of the chromatic number of random graphs

We prove that for every constant >0 the chromatic number of the random graphG(n, p) withp=n ^–1/2– is asymptotically almost surely concentrated in two consecutive values. This implies that for any <1/2 and any integer valued functionr(n)O(n ) there exists a functionp(n) such that the chromatic number ofG(n,p(n)) is preciselyr(n) asymptotically almost surely.Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation.Research supported in part by a Charles Clore Fellowship.     

Admissibility of the natural estimator of the mean of a Gaussian process

Let {X(t): t [a, b]} be a Gaussian process with mean μ L₂[a, b] and continuous covariance K(s, t). When estimating μ under the loss ∫_a^b ( (t)−μ(t))² dt the natural estimator X is admissible if K is unknown. If K is known, X is minimax with risk ∫_a^b K(t, t) dt and admissible if and only if the three by three matrix whose entries are K(t_i, t_j) has a determinant which vanishes identically in t_i [a, b], i = 1, 2, 3.     

Highly linked graphs

A graph with at least 2k vertices is said to bek-linked if, for any choices ₁,...,s _k ,t ₁,...,t _k of 2k distinct vertices there are vertex disjoint pathsP ₁,...,P _k withP _i joinings _i tot _i , 1ik. Recently Robertson and Seymour [16] showed that a graphG isk-linked provided its vertex connectivityk(G) exceeds . We show here thatk(G)22k will do.     

Sparsest solutions of underdetermined linear systems via -minimization for

We present a condition on the matrix of an underdetermined linear system which guarantees that the solution of the system with minimal ℓ_q-quasinorm is also the sparsest one. This generalizes, and slightly improves, a similar result for the ℓ₁-norm. We then introduce a simple numerical scheme to compute solutions with minimal ℓ_q-quasinorm, and we study its convergence. Finally, we display the results of some experiments which indicate that the ℓ_q-method performs better than other available methods.     

Complementary ℓ1-Graphs Embeddable in the Half-Cube

A finite connected graph is called an ℓ₁-graph if it can be isometrically embedded into the space ℓ₁. We complete the classification of pairs of complementaryℓ₁ -graphs started by Deza and Huang, and continued by Shpectorov.     

Stability conditions for systems of linear nonautonomous delay differential equations

Systems of linear nonautonomous delay differential equations are considered which are of the form y′_i(t) = ∑_{k = 1}ⁿ ∝₀^T b_ik(t, s) y_k(t − s) dη_ik(s) − c_i(t) y_i(t), where I = 1,…, n. Sufficient conditions are derived for both the asymptotic stability and the instability of the zero solution. The main result is found by a monotone technique using elementary methods only. Moreover, additional criteria are obtained by using the method of Lyapunov functionals.     

The asymptotic behavior of quadratic forms in -mixing random variables

Let {Z_i,i≥1} be a linear process defined by with {d_j,j≥0} being a regular varying sequence of real numbers and {ξ_t,−∞<t<∞} being a sequence of -mixing random variables. The present paper studies the asymptotic behavior of the quadratic form under some mild assumptions on d_j and ξ_t. Meanwhile, the similar results of α-mixing random variables are presented.     

Enumeration of Planar Constellations

The enumeration of transitive ordered factorizations of a given permutation is a combinatorial problem related to singularity theory. Let n ≥ 1, and let σ₀ be a permutation of _n having d_i cycles of length i, for i ≥ 1. Let m ≥ 2. We prove that the number of m-tuples (σ₁,…,σ_m) of permutation of _n such that

• σσ···σ = σ,

• the group generated by σ,…,σ acts transitively on {1, 2,…,},

• ∑ (σ) = ( − 1) + 2, where (σ) denotes the number of cycles of σ

A one-to-one correspondence relates these m-tuples to some rooted planar maps, which we call constellations and enumerate via a bijection with some bicolored trees. For m = 2, we recover a formula of Tutte for the number of Eulerian maps. The proof relies on the idea that maps are conjugacy classes of trees and extends the method previously applied to Eulerian maps by the second author. Our result might remind the reader of an old theorem of Hurwitz, giving the number of m-tuples of transpositions satisfying the above conditions. Indeed, we show that our result implies Hurwitz' theorem. We also briefly discuss its implications for the enumeration of nonequivalent coverings of the sphere.     

Estimation under ℓ1-Symmetry

The estimation of the location parameter of an ℓ₁-symmetric distribution is considered. Specifically when a p-dimensional random vector has a distribution that is a mixture of uniform distributions on the ℓ₁-sphere, we investigate a general class of estimators of the form δ=X+g. Under the usual quadratic loss, domination of δ over X is obtained through the partial differential inequality 4 div g+2X ∂²g+ g²0 and a new superharmonicity-type-like notion adapted to the ℓ₁-context. Specifically the condition of ℓ₁-superharmonicity is that 2Δf+X ³f0 and div ³f0 as compared to the usual (ℓ₂) condition Δf0.