Repetition-free longest common subsequence

We study the following problem. Given two sequences x and y over a finite alphabet, find a repetition-free longest common subsequence of x and y. We show several algorithmic results, a computational complexity result, and we describe a preliminary experimental study based on the proposed algorithms. We also show that this problem is APX-hard. (C) 2009 Elsevier B.V. All rights reserved.

Application execution management on the InteGrade opportunistic grid middleware

The InteGrade project is a multi-university effort to build a novel grid computing middleware based on the opportunistic use of resources belonging to user workstations. The InteGrade middleware currently enables the execution of sequential, bag-of-tasks, and parallel applications that follow the BSP or the MPI programming models. This article presents the lessons learned over the last five years of the InteGrade development and describes the solutions achieved concerning the support for robust application execution. The contributions cover the related fields of application scheduling, execution management, and fault tolerance. We present our solutions, describing their implementation principles and evaluation through the analysis of several experimental results. (C) 2010 Elsevier Inc. All rights reserved.

Random walks systems with killing on Z

We study random walks systems on Z whose general description follows. At time zero, there is a number N >= 1 of particles at each vertex of N, all being inactive, except for those placed at the vertex one. Each active particle performs a simple random walk on Z and, up to the time it dies, it activates all inactive particles that it meets along its way. An active particle dies at the instant it reaches a certain fixed total of jumps (L >= 1) without activating any particle, so that its lifetime depends strongly on the past of the process. We investigate how the probability of survival of the process depends on L and on the jumping probabilities of the active particles.

RUMOR PROCESSES ON N

We study four discrete-time stochastic systems on N, modeling processes of rumor spreading. The involved individuals can either have an active or a passive role, speaking up or asking for the rumor. The appetite for spreading or hearing the rumor is represented by a set of random variables whose distributions may depend on the individuals. Our goal is to understand-based on the distribution of the random variables-whether the probability of having an infinite set of individuals knowing the rumor is positive or not.

NONHOMOGENEOUS RANDOM WALKS SYSTEMS ON Z

We consider a random walks system on Z in which each active particle performs a nearest-neighbor random walk and activates all inactive particles it encounters. The movement of an active particle stops when it reaches a certain number of jumps without activating any particle. We prove that if the process relies on efficient particles (i.e. those particles with a small probability of jumping to the left) being placed strategically on Z, then it might survive, having active particles at any time with positive probability. On the other hand, we may construct a process that dies out eventually almost surely, even if it relies on efficient particles. That is, we discuss what happens if particles are initially placed very far away from each other or if their probability of jumping to the right tends to I but not fast enough.

Factors associated with increased prevalence of human papillomavirus infection in a cohort of HIV-Infected Brazilian women

Objectives: Human papillomavirus (HPV) infection is a major risk factor for cervical disease. Using baseline data from the HIV-infected cohort of Evandro Chagas Clinical Research Institute at Fiocruz, Rio de Janeiro, Brazil, factors associated with an increased prevalence of HPV were assessed. Methods: Samples from 634 HIV-infected women were tested for the presence of HPV infection using hybrid capture 11 and polymerase chain reaction. Prevalence ratios (PR) were estimated using Poisson regression analysis with robust variance. Results: The overall prevalence of HPV infection was 48%, of which 94% were infected with a high-risk HPV. In multivariate analysis, factors independently associated with infection with high-risk HPV type were: younger age (<30 years of age; PR 1.5, 95% confidence interval (CI) 1.1-2.1), current or prior drug use (PR 1.3, 95% CI 1.0-1.6), self-reported history of HPV infection (PR 1.2, 95% CI 0.96-1.6), condom use in the last sexual intercourse (PR 1.3, 95% CI 1.1-1.7), and nadir CD4+ T-cell count <100 cells/mm(3) (PR 1.6, 95% CI 1.2-2.1). Conclusions: The estimated prevalence of high-risk HPV-infection among HIV-infected women from Rio de Janeiro, Brazil, was high. Close monitoring of HPV-related effects is warranted in all HIV-infected women, in particular those of younger age and advanced immunosuppression. (C) 2008 International Society for Infectious Diseases. Published by Elsevier Ltd. All rights reserved.

HOMEOMORPHISMS OF THE ANNULUS WITH A TRANSITIVE LIFT II

Let f be a homeomorphism of the closed annulus A that preserves the orientation, the boundary components and that has a lift (f) over tilde to the in finite strip (A) over tilde which is transitive. We show that, if the rotation number of (f) over tilde restricted to both boundary components of A is strictly positive, then there exists a closed nonempty connected set Gamma subset of (A) over tilde such that Gamma subset of] - infinity,0] x [0,1], Gamma is unbounded, the projection of to Gamma A is dense, Gamma - (1, 0) subset of Gamma and (f) over tilde(Gamma) subset of Gamma. Also, if p(1) is the projection on the first coordinate of (A) over tilde, then there exists d > 0 such that, for any (z) over tilde is an element of Gamma, lim sup (n ->infinity) p(1)((f) over tilde (n) ((Z) over tilde)) - p(1) ((Z) over tilde)/n < -d.

SUPPORT OF MAXIMIZING MEASURES FOR TYPICAL C(0) DYNAMICS ON COMPACT MANIFOLDS

Given a compact manifold X, a continuous function g : X -> IR, and a map T : X -> X, we study properties of the T-invariant Borel probability measures that maximize the integral of g. We show that if X is a n-dimensional connected Riemaniann manifold, with n >= 2, then the set of homeomorphisms for which there is a maximizing measure supported on a periodic orbit is meager. We also show that, if X is the circle, then the ""topological size"" of the set of endomorphisms for which there are g maximizing measures with support on a periodic orbit depends on properties of the function g. In particular, if g is C(1), it has interior points.

Homeomorphisms of the annulus with a transitive lift

Let f be a homeomorphism of the closed annulus A that preserves the orientation, the boundary components and that has a lift (f) over tilde to the infinite strip (A) over tilde which is transitive. We show that, if the rotation numbers of both boundary components of A are strictly positive, then there exists a closed nonempty unbounded set B(-) subset of (A) over tilde such that B(-) is bounded to the right, the projection of B to A is dense, B - (1, 0) subset of B and (f) over tilde (B) subset of B. Moreover, if p(1) is the projection on the first coordinate of (A) over tilde, then there exists d > 0 such that, for any (z) over tilde is an element of B(-), lim sup (n ->infinity) p1((f) over tilde (n)((z) over tilde)) - p(1) ((z) over tilde)/n < - d. In particular, using a result of Franks, we show that the rotation set of any homeomorphism of the annulus that preserves orientation, boundary components, which has a transitive lift without fixed points in the boundary is an interval with 0 in its interior.

Maximizing measures for endomorphisms of the circle

We study a given fixed continuous function phi : S(1) -> R and an endomorphism f : S(1)-> S(1), whose f-invariant probability measures maximize integral phi d mu. We prove that the set of endomorphisms having a f maximizing invariant measure supported on a periodic orbit is C(0) dense.

On maximizing measures of homeomorphisms on compact manifolds

We prove that given a compact n-dimensional connected Riemannian manifold X and a continuous function g : X -> R, there exists a dense subset of the space of homeomorphisms of X such that for all T in this subset, the integral integral(X) g d mu, considered as a function on the space of all T-invariant Borel probability measures mu, attains its maximum on a measure supported on a periodic orbit.

Genericity of Nondegeneracy for Light Rays in Stationary Spacetimes

Given a Lorentzian manifold (M, g), an event p and an observer U in M, then p and U are light conjugate if there exists a lightlike geodesic gamma : [0, 1] -> M joining p and U whose endpoints are conjugate along gamma. Using functional analytical techniques, we prove that if one fixes p and U in a differentiable manifold M, then the set of stationary Lorentzian metrics in M for which p and U are not light conjugate is generic in a strong sense. The result is obtained by reduction to a Finsler geodesic problem via a second order Fermat principle for light rays, and using a transversality argument in an infinite dimensional Banach manifold setup.

Multiple Brake Orbits and Homoclinics in Riemannian Manifolds

Let (M, g) be a complete Riemannian manifold, Omega subset of Man open subset whose closure is homeomorphic to an annulus. We prove that if a,Omega is smooth and it satisfies a strong concavity assumption, then there are at least two distinct geodesics in starting orthogonally to one connected component of a,Omega and arriving orthogonally onto the other one. Using the results given in Giamb et al. (Adv Differ Equ 10:931-960, 2005), we then obtain a proof of the existence of two distinct homoclinic orbits for an autonomous Lagrangian system emanating from a nondegenerate maximum point of the potential energy, and a proof of the existence of two distinct brake orbits for a class of Hamiltonian systems. Under a further symmetry assumption, the result is improved by showing the existence of at least dim(M) pairs of geometrically distinct geodesics as above, brake orbits and homoclinic orbits. In our proof we shall use recent deformation results proved in Giamb et al. (Nonlinear Anal Ser A: Theory Methods Appl 73:290-337, 2010).

Existence of orthogonal geodesic chords on Riemannian manifolds with concave boundary and homeomorphic to the N-dimensional disk

In this paper we give a proof of the existence of an orthogonal geodesic chord on a Riemannian manifold homeomorphic to a closed disk and with concave boundary. This kind of study is motivated by the link (proved in Giambo et al. (2005) [8]) of the multiplicity problem with the famous Seifert conjecture (formulated in Seifert (1948) [1]) about multiple brake orbits for a class of Hamiltonian systems at a fixed energy level. (C) 2010 Elsevier Ltd. All rights reserved.

On the Multiplicity of Orthogonal Geodesics in Riemannian Manifold With Concave Boundary. Applications to Brake Orbits and Homoclinics

Let (M, g) be a complete Riemannian Manifold, Omega subset of M an open subset whose closure is diffeomorphic to an annulus. If partial derivative Omega is smooth and it satisfies a strong concavity assumption, then it is possible to prove that there are at least two geometrically distinct geodesics in (Omega) over bar = Omega boolean OR partial derivative Omega starting orthogonally to one connected component of partial derivative Omega and arriving orthogonally onto the other one. The results given in [6] allow to obtain a proof of the existence of two distinct homoclinic orbits for an autonomous Lagrangian system emanating from a nondegenerate maximum point of the potential energy, and a proof of the existence of two distinct brake orbits for a. class of Hamiltonian systems. Under a further symmetry assumption, it is possible to show the existence of at least dim(M) pairs of geometrically distinct geodesics as above, brake orbits and homoclinics.