Decomposition algorithms for the tree edit distance problem

We study the behavior of dynamic programming methods for the tree edit distance problem, such as [P. Klein, Computing the edit-distance between unrooted ordered trees, in: Proceedings of 6th European Symposium on Algorithms, 1998, p. 91–102; K. Zhang, D. Shasha, SIAM J. Comput. 18 (6) (1989) 1245–1262]. We show that those two algorithms may be described as decomposition strategies. We introduce the general framework of cover strategies, and we provide an exact characterization of the complexity of cover strategies. This analysis allows us to define a new tree edit distance algorithm, that is optimal for cover strategies.     

Hermite Subdivision Schemes and Taylor Polynomials

We propose a general study of the convergence of a Hermite subdivision scheme ℋ of degree d>0 in dimension 1. This is done by linking Hermite subdivision schemes and Taylor polynomials and by associating a so-called Taylor subdivision (vector) scheme . The main point of investigation is a spectral condition. If the subdivision scheme of the finite differences of is contractive, then is C ⁰ and ℋ is C ^d . We apply this result to two families of Hermite subdivision schemes. The first one is interpolatory; the second one is a kind of corner cutting. Both of them use the Tchakalov-Obreshkov interpolation polynomial.      

Efficient Spatial Modeling Using the SPDE Approach With Bivariate Splines

Gaussian fields (GFs) are frequently used in spatial statistics for their versatility. The associated computational cost can be a bottleneck, especially in realistic applications. It has been shown that computational efficiency can be gained by doing the computations using Gaussian Markov random fields (GMRFs) as the GFs can be seen as weak solutions to corresponding stochastic partial differential equations (SPDEs) using piecewise linear finite elements. We introduce a new class of representations of GFs with bivariate splines instead of finite elements. This allows an easier implementation of piecewise polynomial representations of various degrees. It leads to GMRFs that can be inferred efficiently and can be easily extended to nonstationary fields. The solutions approximated with higher order bivariate splines converge faster, hence the computational cost can be alleviated. Numerical simulations using both real and simulated data also demonstrate that our framework increases the flexibility and efficiency. Supplementary materials are available online.     

Approximation Algorithms for Steiner and Directed Multicuts

In this paper we consider theSteiner multicutproblem. This is a generalization of the minimum multicut problem where instead of separating nodepairs, the goal is to find a minimum weight set of edges that separates all givensetsof nodes. A set is considered separated if it is not contained in a single connected component. We show anO(log³(kt)) approximation algorithm for the Steiner multicut problem, wherekis the number of sets andtis the maximum cardinality of a set. This improves theO(t log k) bound that easily follows from the previously known multicut results. We also consider an extension of multicuts to directed case, namely the problem of finding a minimum-weight set of edges whose removal ensures that none of the strongly connected components includes one of the prespecifiedknode pairs. In this paper we describe anO(log² k) approximation algorithm for this directed multicut problem. Ifk ? n, this represents an improvement over theO(log n log log n) approximation algorithm that is implied by the technique of Seymour.     

Elliptic Interface Problems in Axisymmetric Domains. Part I: Singular Functions of Non - Tensorial Type

We study the regularity of solutions of interface problems for the Poisson equation in axisynunetric domains. The Fourier decomposition of the 3D-problem into a sequence of 2D-variational equations end uniform (with respect to the sequence parameter) a prior; estimates of their solutions are derived. Some non-tensorial singular functions describing the behaviour of the solution near interface edges are given and the smoothness of the stress intensity distribution as well as the tangential regularity are characterized in tenns of Sobolev spaces. In a forthcoming part II of this paper, the results will be applied to error estimates of the so-called Fourier-finite-element method for solving approximately elliptic interface problems in 3D.     

Singular Solutions to Conformal Hessian Equations

The authors show that for any e ∈]0,1[,there exists an analytic outside zero solution to a uniformly elliptic conformal Hessian equation in a ball B C R5 which belongs to C1'ε(B) \ C1'ε+(B).     

Congruence preserving functions on free monoids

A function on an algebra is congruence preserving if for any congruence, it maps congruent elements to congruent elements. We show that on a free monoid generated by at least three letters, a function from the free monoid into itself is congruence preserving if and only if it is of the form \({x \mapsto w_{0}xw_{1} \cdots w_{n-1}xw_n }\) for some finite sequence of words \({w_0,\ldots ,w_n}\). We generalize this result to functions of arbitrary arity. This shows that a free monoid with at least three generators is a (noncommutative) affine complete algebra. As far as we know, it is the first (nontrivial) case of a noncommutative affine complete algebra.