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,Σ).     

Linear time algorithm for the longest common repeat problem

Given a set of strings U={T₁,T₂,…,T_ℓ}, the longest common repeat problem is to find the longest common substring that appears at least twice in each string of U. We also consider reversed and reverse-complemented repeats as well as normal repeats. We present a linear time algorithm for the longest common repeat problem.     

Two-pattern strings II—frequency of occurrence and substring complexity

The previous paper in this series introduced a class of infinite binary strings, called two-pattern strings, that constitute a significant generalization of, and include, the much-studied Sturmian strings. The class of two-pattern strings is a union of a sequence of increasing (with respect to inclusion) subclasses T_λ of two-pattern strings of scope λ, λ=1,2,…. Prefixes of two-pattern strings are interesting from the algorithmic point of view (their recognition, generation, and computation of repetitions and near-repetitions) and since they include prefixes of the Fibonacci and the Sturmian strings, they merit investigation of how many finite two-pattern strings of a given size there are among all binary strings of the same length. In this paper we first consider the frequency f_λ(n) of occurrence of two-pattern strings of length n and scope λ among all strings of length n on {a,b}: we show that lim_n→∞f_λ(n)=0, but that for strings of lengths n2λ, two-pattern strings of scope λ constitute more than one-quarter of all strings. Since the class of Sturmian strings is a subset of two-pattern strings of scope 1, it was natural to focus the study of the substring complexity of two-pattern strings to those of scope 1. Though preserving the aperiodicity of the Sturmian strings, the generalization to two-pattern strings greatly relaxes the constrained substring complexity (the number of distinct substrings of the same length) of the Sturmian strings. We derive upper and lower bounds on C₁(k) (the number of distinct substring of length k) of two-pattern strings of scope 1, and we show that it can be considerably greater than that of a Sturmian string. In fact, we describe circumstances in which lim_k→∞(C₁(k)−k)=∞.     

Character sets of strings

Given a string S over a finite alphabet Σ, the character set (also called the fingerprint) of a substring S^′ of S is the subset CΣ of the symbols occurring in S^′. The study of the character sets of all the substrings of a given string (or a given collection of strings) appears in several domains such as rule induction for natural language processing or comparative genomics. Several computational problems concerning the character sets of a string arise from these applications, especially:

(1) Output all the maximal locations of substrings having a given character set.

(2) Output for each character set C occurring in a given string (or a given collection of strings) all the maximal locations of C.

Denoting by n the total length of the considered string or collection of strings, we solve the first problem in Θ(n) time using Θ(n) space. We present two algorithms solving the second problem. The first one runs in Θ(n²) time using Θ(n) space. The second algorithm has Θ(n|Σ|log|Σ|) time and Θ(n) space complexity and is an adaptation of an algorithm by Amir et al. [A. Amir, A. Apostolico, G.M. Landau, G. Satta, Efficient text fingerprinting via Parikh mapping, J. Discrete Algorithms 26 (2003) 1–13].     

Special uniform approximations of continuous vector-valued functions. Part II: special approximations in CX(T)CY(S)

In this paper, which is a continuation of Timofte (J. Approx. Theory 119 (2002) 291–299, we give special uniform approximations of functions from C_XY(T×S) and C_∞(T×S,XY) by elements of the tensor products C_X(T)C_Y(S), respectively C₀(T,X)C₀(S,Y), for topological spaces T,S and Γ-locally convex spaces X,Y (all four being Hausdorff).     

On improved estimators of the generalized variance

Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p W_p(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ I_k) with ξ(p × k) unknown. Denote the columns of X by X₍₁₎ ,…, X_(k) and set ψ⁽⁰⁾(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ⁽ⁱ⁾(X, X) = min[ψ⁽ⁱ⁻¹⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |] and Ψ⁽ⁱ⁾(S, X) = min[ψ⁽⁰⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ⁽⁰⁾(S, X) is dominated by each of Ψ⁽ⁱ⁾(S, X), i = 1,…,k and for every i, ψ⁽ⁱ⁾(S, X) is better than ψ⁽ⁱ⁻¹⁾(S, X). In particular, ψ^(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X₍₁₎X′₍₁₎|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X₍₁₎X′₍₁₎ + + X_(k)X′_(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.     

Bivariate Tensor-Product B-Splines in a Partly Linear Model

In some applications, the mean or median response is linearly related to some variables but the relation to additional variables are not easily parameterized. Partly linear models arise naturally in such circumstances. Suppose that a random sample {(T_i, X_i, Y_i),i=1, 2, …, n} is modeled byY_i=X^T_iβ₀+g₀(T_i)+error_i, whereY_iis a real-valued response,X_iR^pandT_iranges over a unit square, andg₀is an unknown function with a certain degree of smoothness. We make use of bivariate tensor-product B-splines as an approximation of the functiong₀and consider M-type regression splines by minimization of ∑ⁿ_i=1 ρ(Y_i−X^T_iβ−g_n(T_i)) for some convex functionρ. Mean, median and quantile regressions are included in this class. We show under appropriate conditions that the parameter estimate ofβachieves its information bound asymptotically and the function estimate ofg₀attains the optimal rate of convergence in mean squared error. Our asymptotic results generalize directly to higher dimensions (for the variableT) provided that the functiong₀is sufficiently smooth. Such smoothness conditions have often been assumed in the literature, but they impose practical limitations for the application of multivariate tensor product splines in function estimation. We also discuss the implementation of B-spline approximations based on commonly used knot selection criteria together with a simulation study of both mean and median regressions of partly linear models.     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

Consistency of a recursive nearest neighbor regression function estimate

Let (X, Y) be an ^d × -valued random vector and let (X₁, Y₁),…,(X_N, Y_N) be a random sample drawn from its distribution. Divide the data sequence into disjoint blocks of length l₁, …, l_n, find the nearest neighbor to X in each block and call the corresponding couple (X_i^*, Y_i^*). It is shown that the estimate m_n(X) = Σ_{i = 1}ⁿ w_niY_i^*/Σ_{i = 1}ⁿ w_ni of m(X) = E{Y|X} satisfies E{|m_n(X) − m(X)|^p} 0 (p ≥ 1) whenever E{|Y|^p} < ∞, l_n ∞, and the triangular array of positive weights {w_ni} satisfies sup_{i ≤ n}w_ni/Σ_{i = 1}ⁿ w_ni 0. No other restrictions are put on the distribution of (X, Y). Also, some distribution-free results for the strong convergence of E{|m_n(X) − m(X)|^p|X₁, Y₁,…, X_N, Y_N} to zero are included. Finally, an application to the discrimination problem is considered, and a discrimination rule is exhibited and shown to be strongly Bayes risk consistent for all distributions.     

Comonotone approximation of twice differentiable periodic functions

In the case where a 2π-periodic function f is twice continuously differentiable on the real axis ℝ and changes its monotonicity at different fixed points y _i ∈ [− π, π), i = 1,…, 2s, s ∈ ℕ (i.e., on ℝ, there exists a set Y := {y _i } _i∈ℤ of points y _i = y _i+2s + 2π such that the function f does not decrease on [y _i , y _i−1] if i is odd and does not increase if i is even), for any natural k and n, n ≥ N(Y, k) = const, we construct a trigonometric polynomial T _n of order ≤n that changes its monotonicity at the same points y _i ∈ Y as f and is such that

A Remark on Self-Normalization for Dependent Random Variables

Let (X _t , t ∈ Z) be a stationary process, and let S _n = ∑_{1⩽ i⩽n} X _i . In this paper, we consider the central limit theorem for the self-normalized sequence S _n /U _n , where U _n ² = ∑_1⩽j⩽N Y _j ² , Y _j = ∑_{(j−1)m<i⩽jm} X _i , n = mN. We show how such a self-normalization works for AR(1) and MA(q) processes.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 2, pp. 173–183, April–June, 2005.     

A note on asymptotic expansions for Markov chains using operator theory

We consider asymptotic expansions for sums S_n on the form S_n = ƒ₀(X₀) + ƒ(X₁, X₀) + … + ƒ(X_n, X_n−1), where X_i is a Markov chain. Under different ergodicity conditions on the Markov chain and certain conditional moment conditions on ƒ(X_i, X_i−1), a simple representation of the characteristic function of S_n is obtained. The representation is in term of the maximal eigenvalue of the linear operator sending a function g(x) into the function x → E(g(X_i)exp[itƒ(X_i, x)]|X_i−1 = x).     

A random CLT for dependent random variables

We introduce a new condition for {Y_τn} to have the same asymptotic distribution that {Y_n} has, where {Y_n} is a sequence of random elements of a metric space (S, d) and {τ_n} is a sequence of random indices. The condition on {Y_n} is that max_iDnd(Y_i, Y_an)→^p0 as n → ∞, where D_n = {i: |k_i−k_an| ≤ δ_ank_an} and {δ_n} is a nonincreasing sequence of positive numbers. The condition on {τ_n} is that P(|(k_τn/k_an)−1| > δ_an) → 0 as n → ∞. Under these conditions, we will show that d(Y_τn, Y_an) → ^P0 and apply this result to the CLT for a general class of sequences of dependent random variables.     

FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

A full-invariant theorem and some applications

Let (X,τ₁) and (Y,τ₂) be two Hausdorff locally convex spaces with continuous duals X′ and Y′, respectively, L(X,Y) be the space of all continuous linear operators from X into Y, K(X,Y) be the space of all compact operators of L(X,Y). Let WOT and UOT be the weak operator topology and uniform operator topology on K(X,Y), respectively. In this paper, we characterize a full-invariant property of K(X,Y); that is, if the sequence space λ has the signed-weak gliding hump property, then each λ-multiplier WOT-convergent series ∑_iT_i in K(X,Y) must be λ-multiplier convergent with respect to all topologies between WOT and UOT if and only if each continuous linear operator T :(X,τ₁)→(λ^β,σ(λ^β,λ)) is compact. It follows from this result that the converse of Kalton's Orlicz–Pettis theorem is also true.     

Some Properties of Nonstar Steps in Addition Chains and New Cases Where the Scholz Conjecture Is True

Let ℓ(n) be the smallest possible length of addition chains for a positive integer n. Then Scholz conjectured that ℓ(2ⁿ − 1) ≤ n + ℓ(n) − 1, which still remains open. It is known that the Scholz conjecture is true when ν(n) ≤ 4, where ν(n) is the number of 1's in the binary representation of n. In this paper, we give some properties of nonstar steps in addition chains and prove that the Scholz conjecture is true for infinitely many new integers including the case where ν(n) = 5.     

The asymptotic ruin problem when the healthy and sick periods form an alternating renewal process

Let {T₁, Y₁}^∞_i=1 be a sequence of positive independent random variables. Let, also, Z₁ = βY′₁ ? πT_i, i = 1, 2, …, where Y′₁ = Max(0, Y_i ? w), w ? 0, and where β < 0 and π is such that E(Z₁) < 0. We consider the random walk of partial sums S_n = ?ⁿ_i=1Z_i in the presence of an absorbing region (u, ∞), u ? 0, and S₀ ≡ 0. Of interest is $\text{ψ(u) = Pr(}\text{S}\text{?}\text{≤ u)}$ where S? = Sup(0, S₁, S₂, …, S_n, …).     

Approximations of Two-Place Functions by Finite Sums of Terms with Separable Variables

It is known that if a smooth function h in two real variables x and y belongs to the class Σ_n of all sums of the form Σⁿ_k=1ƒ_k(x) g_k(y), then its (n + 1)th order "Wronskian" det[h_xⁱy^j]ⁿ_i,j=0 is identically equal to zero. The present paper deals with the approximation problem h(x, y) Σⁿ_k=1ƒ_k(x) g_k(y) with a prescribed n, for general smooth functions h not lying in Σ_n. Two natural approximation sums T=T(h) Σ_n, S=S(h) Σ_n are introduced and the errors |h-T|, |h-S| are estimated by means of the above mentioned Wronskian of the function h. The proofs utilize the technique of ordinary linear differential equations.     

Twisting geometric codes

The aim of this paper is to explain how, starting from a Goppa code C(X,G,P₁,…,P_n) and a cyclic covering π:Y→X of degree m, one can twist the initial code to another one C(X,G+D_χ,P₁,…,P_n), where D_χ is a non-principal degree 0 divisor on X associated to a character χ of Gal(Y/X), in the hope that ℓ_X(G+D_χ)>ℓ_X(G). We give, using a MAGMA program, several examples where this occurs, and where both the initial and twisted codes have same minimum distance, so that initial codes have been improved.     

Schur functions and the invariant polynomials characterizing U(n) tensor operators

We give a direct formulation of the invariant polynomials _μG_q⁽ⁿ⁾(, Δ_i,;, x_{i,i + 1},) characterizing U(n) tensor operators p, q, …, q, 0, …, 0 in terms of the symmetric functions S_λ known as Schur functions. To this end, we show after the change of variables Δ_i = γ_i − δ_i and x_{i, i + 1} = δ_i − δ_{i + 1} that_μG_q⁽ⁿ⁾(,Δ_i;, x_{i, i + 1},) becomes an integral linear combination of products of Schur functions S_α(, γ_i,) · S_β(, δ_i,) in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}, respectively. That is, we give a direct proof that _μG_q⁽ⁿ⁾(,Δ_i,;, x_{i, i + 1},) is a bisymmetric polynomial with integer coefficients in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}. By making further use of basic properties of Schur functions such as the Littlewood-Richardson rule, we prove several remarkable new symmetries for the yet more general bisymmetric polynomials _μ^mG_q⁽ⁿ⁾(γ₁,…, γ_n; δ₁,…, δ_m). These new symmetries enable us to give an explicit formula for both _μ^mG₁⁽ⁿ⁾(γ; δ) and ₁G₂⁽ⁿ⁾(γ; δ). In addition, we describe both algebraic and numerical integration methods for deriving general polynomial formulas for _μ^mG_q⁽ⁿ⁾(γ; δ).