Computing a longest common subsequence for a set of strings

The known 2-string LCS problem is generalized to finding a Longest Common Subsequence (LCS) for a set of strings. A new, general approach that systematically enumerates common subsequences is proposed for the solution. Assuming a finite symbol set, it is shown that the presented scheme requires a preprocessing time that grows linearly with the total length of the input strings and a processing time that grows linearly with (K), the number of strings, and () the number of matches among them. The only previous algorithm for the generalized LCS problem takesO(K·|S ₁|·|S ₂|·...|S _k |) execution time, where |S _i | denotes the length of the stringS _i . Since typically is a very small percentage of |S ₁|·|S ₂|·...·|S _k |, the proposed method may be considered to be much more efficient than the straightforward dynamic programming approach.     

Some Landau's type inequalities for infinitesimal generators

Summary Lett T(t) be a strongly continuous contraction semigroup on a complex Banach space and letA be its infinitesimal generator. We prove that, forx D(A ³), the following inequalities hold true: Ax³ 243/8 x²A ³ x, A ² x 24 xA ³ x². Ift T(t) is a contraction group (resp. cosine function) we get the analogous but better inequalities with constants 9/8 and 3 (resp. 81/40 and 72/25) instead of 243/8 and 24. We consider also uniformly bounded semigroups, groups and cosine functions.     

Daugavet type inequalities for operators on L p–spaces

Let T be a regular operator from L ^p L ^p. Then , where T_r denotes the regular norm of T, i.e., T_r=|T| where |T| denotes the modulus operator of a regular operator T. For p=1 every bounded linear operator is regular and T=T_r, so that the above inequality generalizes the Daugavet equation for operators on L ¹–spaces. The main result of this paper (Theorem 9) is a converse of the above result. Let T be a regular linear operator on L _p and denote by T _A the operator T_A. Then for all A with (A)>0 if and only if .     

A global pinching theorem for compact surfaces inS 3 with constant mean curvature

LetM be a compact minimal surface inS ³. Y. J. Hsu^[5] proved that if S₂22, thenM is either the equatorial sphere or the Clifford torus, whereS is the square of the length of the second fundamental form ofM, ·₂ denotes theL ²-norm onM. In this paper, we generalize Hsu's result to any compact surfaces inS ³ with constant mean curvature.Supported by NSFH.     

Fehlerabschätzungen für Gauß-Quadraturformeln

Summary We consider Gauss quadrature formulaeQ _n ,n, approximating the integral ,w an even weight function. Let be analytic inK _r :={z:|z|<r},r>1, and . The error functionalR _n :=I-Q _n is continuous with respect to |·|_r and the relation , q_2k (x):=x ^2k holds.In this paper estimates for R _n are given. To this end we first derive two new representations of R _n which are essential for our further investigations. The R _n =r ² R _n (), with (x):=1/(r ²-x ²), is estimated in various ways by using the best uniform approximation of in P_2n-1, and also the expansion of with respect to Chebyshe polynomials of the first and second kind. Forw(x)=(1-x ²), =±1/2, R _n is calculated. The asymptotic behaviour, forr1+, of R _n and of the derived error bounds is also discussed. Finally, we compare different error bounds and give numerical examples.

     

Quadratic spline interpolation on uniform meshes

The interpolation problem at uniform mesh points of a quadratic splines(x _i)=f _i,i=0, 1,...,N ands(x ₀)=f₀ is considered. It is known that s–f=O(h ³) and s–f=O(h ²), whereh is the step size, and that these orders cannot be improved. Contrary to recently published results we prove that superconvergence cannot occur for any particular point independent off other than mesh points wheres=f by assumption. Best error bounds for some compound formulae approximatingf _i andf _i ⁽³⁾ are also derived.     

Jordan axioms for C*-algebras

A complex Banach spaceA which is also an associative algebra provided with a conjugate linear vector space involution * satisfying (a ²)^*=(a ^*)², aa ^* a=a³ and ab+ba2ab for alla, b inA is shown to be a C^*-algebra. The assumptions onA can be expressed in terms of the Jordan algebra obtained by symmetrization of the product ofA and are satisfied by any C^*-algebra. Thus we obtain a purely Jordan characterization of C^*-algebras.     

Approximating derivations on ideals ofC *-algebras

For each^*-derivation of a separableC ^*-algebraA and each >0 there is an essential idealI ofA and a self-adjoint multiplierx ofI such that (–ad(ix))|I< and x.     

L p -estimates for the solutions of second order elliptic equations

Summary We investigate the homogeneous Dirichlet problem in H^2,p for a second order elliptic partial differential equation in nondivergence form Lu=f in the case in which the leading coefficients of L belong to H^1,n(), Rⁿ. We prove that if p belongs to a suitable neighbourhood of 2, then the above problem, has a unique solution u satisfying D²u_p Cf_p; furthermore, if f H^k,p, k=1,2, ..., and the coefficients of L satisfy some natural conditions, then the solution satisfies .Lavoro eseguito nell'ambito del gruppi 40% e 60% del M.P.I.     

Symmetrization of functions in Sobolev spaces and the isoperimetric inequality

A positive measurable function f on R^d can be symmetrized to a function f^* depending only on the distance r, and with the same distribution function as f. If the distribution derivatives of f are Radon measures then we have the inequality f^*f, where f is the total mass of the gradient. This inequality is a generalisation of the classical isoperimetric inequality for sets. Furthermore, and this is important for applications, if f belongs to the Sobolev space H¹,P then f^* belongs to H¹,P and f^*_pf_p.     

Isomorphismen von rechtseiträumen

Spaces called rectangular spaces were introduced in [5] as incidence spaces (P,G) whose set of linesG is equipped with an equivalence relation and whose set of point pairs P² is equipped with a congruence relation , such that a number of compatibility conditions are satisfied. In this paper we consider isomorphisms, automorphisms, and motions on the rectangular spaces treated in [5]. By an isomorphism of two rectangular spaces (P,G, , ) and (P,G, , ) we mean a bijection of the point setP onto P which maps parallel lines onto parallel lines and congruent points onto congruent points. In the following, we consider only rectangular spaces of characteristic 2 or of dimension two. According to [5] these spaces can be embedded into euclidean spaces. In case (P,G, , ) is a finite dimensional rectangular space, then every congruence preserving bijection ofP onto P is in fact an isomorphism from (P,G, , ) onto (P,G, , ) (see (2.4)). We then concern ourselves with the extension of isomorphisms. Our most important result is the theorem which states that any isomorphism of two rectangular spaces can be uniquely extended to an isomorphism of the associated euclidean spaces (see (3.2)). As a consequence the automorphisms of a rectangular space (P,G, , ) are precisely the restrictions (onP) of the automorphisms of the associated euclidean space which fixP as a whole (see (3.3)). Finally we consider the motions of a rectangular space (P,G, , ). By a motion of(P. G,, ) we mean a bijection ofP which maps lines onto lines, preserves parallelism and satisfies the condition((x), (y)) (x,y) for allx, y P. We show that every motion of a rectangular space can be extended to a motion of the associated euclidean space (see (4.2)). Thus the motions of a rectangular space (P,G, , ) are seen to be the restrictions of the motions of the associated euclidean space which mapP into itself (see (4.3)). This yields an explicit representation of the motions of any rectangular plane (see (4.4)).

---

---

Herrn Professor Burau zum 85. Geburtstag gewidmet     

Ein neues Surjektivitätskriterium im Hilbertraum

LetA, B andC be linearm-accretive operators in a Hilbert space. Suppose further thatC is bounded, thatb:=inf {Re (C y, y)| y=1}>0, thatA ^–1 exists as a bounded operator and that Re (B ^* x, A ^–1 x)+a x²0 holds for allxD (B ^*) and a constanta with 0a<b. ThenCA+B is surjective, (CA+B)^–1 exists and C Ax+Bx (b–a) A x holds for allxD (A) D (B). This criterion can be applied to evolution equations of the formdu/dt+C(t)A(t)u=f(t) whereB:=d/dt.     

Blow-up of solutions of nonlinear wave equations in three space dimensions

Let u(x,t) be a solution, uA|u|^p for xIR₃, t0 where is the d'Alembertian, and A, p are constants with A>0, 10–|x–x⁰|, if the initial data u(x,0), u_t(x,0) have their support in the ball |x–x⁰|t₀. In particular global solutions of u=A|u|^p with initial data of compact support vanish identically. On the other hand for A>0, p>1+2 global solutions of u=A|u|^p exist, if the initial data are of compact support and u is sufficiently small in a suitable norm. For p=2 the time at which u becomes infinite is of order u^–2.Dedicated to Hans Lewy and Charles B. Morrey, Jr.The research for this paper was performed at the Courant Institute and supported by the Office of Naval Research under Contract No. N00014-76-C-0301. Reproduction in whole or part is permitted for any purpose of the United States Government.     

Sufficient conditions for bang-bang control in Hilbert space

Sufficient conditions for bang-bang and singular optimal control are established in the case of linear operator equations with cost functionals which are the sum of linear and quadratic terms, that is,Ax=u,J(u)=(r,x)+(x,x), >0. For example, ifA is a bounded operator with a bounded inverse from a Hilbert spaceH into itself and the control setU is the unit ball inH, then an optimal control is bang-bang (has norm l) if 0<1/2;A ^–1*r·A ^–1–2, but is singular (an interior point ofU) if >1/2A ^–1*r·A².This work was supported by NRC Grant No. A-4047 and NSF Grant No. GP-7445.     

Quadratically constrained least squares and quadratic problems

Summary We consider the following problem: Compute a vectorx such that Ax–b₂=min, subject to the constraint x₂=. A new approach to this problem based on Gauss quadrature is given. The method is especially well suited when the dimensions ofA are large and the matrix is sparse.It is also possible to extend this technique to a constrained quadratic form: For a symmetric matrixA we consider the minimization ofx ^T A x–2b ^T x subject to the constraint x₂=.Some numerical examples are given.This work was in part supported by the National Science Foundation under Grant DCR-8412314 and by the National Institute of Standards and Technology under Grant 60NANB9D0908.     

Some analytical properties of γ-convex functions on the real line

This paper deals with the analytical properties of -convex functions, which are defined as those functions satisfying the inequalityf(x ₁ )+f(x ₂ )f(x ₁)+f(x ₂), forx _i [x ₁,x ₂], |x _i –x _i |=, i=1,2, whenever |x ₁–x ₂|>, for some given positive . This class contains all convex functions and all periodic functions with period . In general, -convex functions do not have ideal properties as convex functions. For instance, there exist -convex functions which are totally discontinuous or not locally bounded. But -convex functions possess so-called conservation properties, meaning good properties which remain true on every bounded interval or even on the entire domain, if only they hold true on an arbitrary closed interval with length . It is shown that boundedness, bounded variation, integrability, continuity, and differentiability almost everywhere are conservation properties of -convex functions on the real line. However, -convex functions have also infection properties, meaning bad properties which propagate to other points, once they appear somewhere (for example, discontinuity). Some equivalent properties of -convexity are given. Ways for generating and representing -convex functions are described.This research was supported by the Deutsche Forschungsgemeinschaft. The first author thanks Prof. Dr. E. Zeidler and Prof. Dr. H. G. Bock for their hospitality and valuable support.     

A geometric property of extremal surfaces

Let the surface R³ be defined by the equation z = f(x, y), where f(x, y) is a function 3 times continuously differentiable in R². It is proved that if the total (Gaussian) curvature of the surface is nonzero almost everywhere on in the sense of Lebesgue measure in R²), then is extremal, i.e., for almost all (x,y) R² the inequality max (||qx||, ||qy, qf (x, y)) > q^–1/s–. holds for all integral q qo (f), where x is the distance from the real number x to the nearest integer and > 0 is arbitrarily small.Translated from Matematicheskie Zametki, Vol. 23, No. 2, pp. 177–181, February, 1978.In conclusion, the author thanks V. G. Sprindzhuk for suggesting the problem.     

Divergent Fourier series with respect to orthonormalized systems of smooth functions

In this paper it is proved that for any functionf L ² [–; ], f>0, there exists a complete orthonormalized system of uniformly bounded trigonometric polynomials with respect to which the Fourier series of this function is divergent almost everywhere in the interval [–; ].Translated from Matematicheskie Zametki, Vol. 20, No. 1, pp. 69–78, July, 1976.The authoress expresses her gratitude to A. M.     

Stationary Gaussian processes with a finite correlation function

If the correlation function vanishes outside the segment [–R, R], then an upper estimate (uniform with respect to all such processes) is possible for the probability of the fact that on an other segment [–r, r] the process remains between – and . Such an estimate is obtained, decreasing for 0 asexp(–f(r/R ln ²+ ) and, moreover,r/R may be either 0 or +. The proof is based on an estimate of the form P_mQ_n c_mn P_m Q_n for norms of polynomials on a circle in the complex plane.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 184, pp. 279–288, 1990.     

On the exactness of a theorem of Mazur and Orlicz

For a preassigned unbounded sequence {S_n} of complex numbers, and preassigned complex numbers z₁ and z₂z₁ we construct: 1) regular matrices A=a_nk and B=b_nk such that the same bounded sequences are summable by these matrices and that , and ; 2) regular matrices A⁽¹⁾)=a _nk ⁽¹⁾ and B⁽¹⁾=b _nk ⁽¹⁾ such that B⁽¹⁾ A⁽¹⁾, and, . Our results show that the well known theorem of MazurOrlicz on the bounded consistency of two regular matrices, one of which is boundedly stronger than the other, is exact.Translated from Matematicheskie Zametki, Vol. 11, No. 4, pp. 431–436, April, 1972.