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.     

Interfacial dynamics‐based modelling of turbulent cavitating flows,Part‐2: Time‐dependent computations

The interfacial dynamics‐based cavitation model, developed in Part‐1, is further employed for unsteady flow computations. The pressure‐based operator‐splitting algorithm (PISO) is extended to handle the time‐dependent cavitating flows with particular focus on the coupling of the cavitation and turbulence models, and the large density ratio associated with cavitation. Furthermore, the compressibility effect is important for unsteady cavitating flows because in a water–vapour mixture, depending on the composition, the speed of sound inside the cavity can vary by an order of magnitude. The implications of the issue of the speed of the sound are assessed with alternative modelling approaches. Depending on the geometric confinement of the nozzle, compressibility model and cavitation numbers, either auto‐oscillation or quasi‐steady behaviour is observed. The adverse pressure gradient in the closure region is stronger at the maximum cavity size. One can also observe that the mass transfer process contributes to the cavitation dynamics. Compared to the steady flow computations, the velocity and vapour volume fraction distributions within the cavity are noticeably improved with time‐dependent computations. Copyright © 2004 John Wiley & Sons, Ltd.     

Tomography of Binomial States of the Radiation Field

The symplectic, optical, and photon-number tomographic symbols of binomial states of the radiation field are studied. Explicit relations for all tomograms of the binomial states are obtained. Two measures for nonclassical properties of these states are discussed.     

Construction of best Bregman approximations in reflexive Banach spaces

An iterative method is proposed to construct the Bregman projection of a point onto a countable intersection of closed convex sets in a reflexive Banach space.

     

Structural properties and tractability results for linear synteny

The syntenic distance between two species is the minimum number of fusions, fissions, and translocations required to transform one genome into the other. The linear syntenic distance, a restricted form of this model, has been shown to be close to the syntenic distance. Both models are computationally difficult to compute and have resisted efficient approximation algorithms with non-trivial performance guarantees. In this paper, we prove that many useful properties of syntenic distance carry over to linear syntenic distance. We also give a reduction from the general linear synteny problem to the question of whether a given instance can be solved using the maximum possible number of translocations. Our main contribution is an algorithm exactly computing linear syntenic distance in nested instances of the problem. This is the first polynomial time algorithm exactly solving linear synteny for a non-trivial class of instances. It is based on a novel connection between the syntenic distance and a scheduling problem that has been studied in the operations research literature.     

A strong law of large numbers for generalized random sets from the viewpoint of empirical processes

In this article we prove a strong law of large numbers for Borel measurable nonseparably valued random elements in the case of generalized random sets.

     

Minimum Disparity Estimation in Linear Regression Models: Distribution and Efficiency

This paper deals with the minimum disparity estimation in linear regression models. The estimators are defined as statistical quantities which minimize the blended weight Hellinger distance between a weighted kernel density estimator of errors and a smoothed model density of errors. It is shown that the estimators of the regression parameters are asymptotic normally distributed and efficient at the model if the weights of the density estimators are appropriately chosen.     

L1-optimal estimates for a regression type function in R

Let X₁, X₂, …, X_n be random vectors that take values in a compact set in R^d, d ≥ 1. Let Y₁, Y₂, …, Y_n be random variables (“the responses”) which conditionally on X₁ = x₁, …, X_n = x_n are independent with densities f(y | x_i, θ(x_i)), i = 1, …, n. Assuming that θ lives in a sup-norm compact space Θ_q,d of real valued functions, an optimal L₁-consistent estimator of θ is constructed via empirical measures. The rate of convergence of the estimator to the true parameter θ depends on Kolmogorov's entropy of Θ_q,d.