An all-substrings common subsequence algorithm

Given two strings A and B of lengths n(a) and n(b), n(a) <= n(b), respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B` of B, the length of the longest string that is a subsequence of both A and B. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n(a)n(b)) time and O(n(a) + n(b)) space. After this preparation, it is possible to build that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and a matrix of size O(n(b)(2)) the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem. (C) 2007 Elsevier B.V. All rights reserved.

Solvatochromic Shift of the pi -> pi* Transition in All-Trans, Cis-13, Cis-11, Cis-9, and Cis-7 Retinal Isomers Induced by Water and Methanol

The solvatochromic shift of the lowest singlet it pi -> pi* electronic transition in the all-trans, cis-13, cis-11, cis-9, and cis-7 retinal isomers were computed under the influence of water, methanol, and benzene solvents. Excitation energies were calculated in gas phase and in solution. The calculations in solution were performed considering the sequential Monte Carlo (MC) /Quantum Mechanical approach. The MC simulations were performed considering the full retinal isomer molecules and 900 water molecules, 900 methanol, or 400 benzene ones. The OPLS/AA parametrization was chosen for retinal, methanol, and benzene molecules and the SPC model was used for water one. From the MC calculations 100 independent configurations were selected, with 100 solvent molecules in thermodynamical equilibrium at T = 298.15 K. Average point-charges were obtained from those independent configurations for water, methanol, and benzene solvent. TDDFT and CASSCF//CASPT2 methodologies were used to compute the vertical excitation energy of the retinal isomers in different environment. (C) 2010 Wiley Periodicals, Inc. Int J Quantum Chem 110: 2076-2087, 2010

Effect of different ferrule designs on the fracture resistance and failure pattern of endodontically treated teeth restored with fiber posts and all-ceramic crowns

OBJECTIVE: This study investigated the effect of different ferrule heights on endodontically treated premolars. MATERIAL AND METHODS: Fifty sound mandibular first premolars were endodontically treated and then restored with 7-mm fiber post (FRC Postec Plus #1 Ivoclar-Vivadent) luted with self-polymerized resin cement (Multilink, Ivoclar Vivadent) while the coronal section was restored with hybrid composite core build-up material (Tetric Ceram, Ivoclar-Vivadent), which received all-ceramic crown. Different ferrule heights were investigated: 1-mm circumferential ferrule without post and core (group 1 used as control), a circumferential 1-mm ferrule (group 2), non-uniform ferrule 2-mm buccally and 1-mm lingually (group 3), non-uniform ferrule 3-mm buccally and 2-mm lingually (group 4), and finally no ferrule preparation (group 5). The fracture load and failure pattern of the tested groups were investigated by applying axial load to the ceramic crowns (n=10). Data were analyzed statistically by one-way ANOVA and Tukey's post-hoc test was used for pair-wise comparisons (α=0.05). RESULTS: There were no significant differences among the failure load of all tested groups (P<0.780). The control group had the lowest fracture resistance (891.43±202.22 N) and the highest catastrophic failure rate (P<0.05). Compared to the control group, the use of fiber post reduced the percentage of catastrophic failure while increasing the ferrule height did not influence the fracture resistance of the restored specimens. CONCLUSIONS: Within the limitations of this study, increasing the ferrule length did not influence the fracture resistance of endodontically treated teeth restored with glass ceramic crowns. Insertion of a fiber post could reduce the percentage of catastrophic failure of these restorations under function.

UNIQUENESS AND NONUNIQUENESS RESULTS FOR A CERTAIN CLASS OF ALMOST PERIODIC DISTRIBUTIONS

We consider distributions u is an element of S'(R) of the form u(t) = Sigma(n is an element of N) a(n)e(i lambda nt), where (a(n))(n is an element of N) subset of C and Lambda = (lambda n)(n is an element of N) subset of R have the following properties: (a(n))(n is an element of N) is an element of s', that is, there is a q is an element of N such that (n(-q) a(n))(n is an element of N) is an element of l(1); for the real sequence., there are n(0) is an element of N, C > 0, and alpha > 0 such that n >= n(0) double right arrow vertical bar lambda(n)vertical bar >= Cn(alpha). Let I(epsilon) subset of R be an interval of length epsilon. We prove that for given Lambda, (1) if Lambda = O(n(alpha)) with alpha < 1, then there exists epsilon > 0 such that u vertical bar I(epsilon) = 0 double right arrow u 0; (2) if Lambda = O(n) is uniformly discrete, then there exists epsilon > 0 such that u vertical bar I(epsilon) = 0 double right arrow u 0; (3) if alpha > 1 and. is uniformly discrete, then for all epsilon > 0, u vertical bar I(epsilon) = 0 double right arrow u = 0. Since distributions of the above mentioned form are very common in engineering, as in the case of the modeling of ocean waves, signal processing, and vibrations of beams, plates, and shells, those uniqueness and nonuniqueness results have important consequences for identification problems in the applied sciences. We show an identification method and close this article with a simple example to show that the recovery of geometrical imperfections in a cylindrical shell is possible from a measurement of its dynamics.

Dynamical models for computer viruses propagation

Nowadays, digital computer systems and networks are the main engineering tools, being used in planning, design, operation, and control of all sizes of building, transportation, machinery, business, and life maintaining devices. Consequently, computer viruses became one of the most important sources of uncertainty, contributing to decrease the reliability of vital activities. A lot of antivirus programs have been developed, but they are limited to detecting and removing infections, based on previous knowledge of the virus code. In spite of having good adaptation capability, these programs work just as vaccines against diseases and are not able to prevent new infections based on the network state. Here, a trial on modeling computer viruses propagation dynamics relates it to other notable events occurring in the network permitting to establish preventive policies in the network management. Data from three different viruses are collected in the Internet and two different identification techniques, autoregressive and Fourier analyses, are applied showing that it is possible to forecast the dynamics of a new virus propagation by using the data collected from other viruses that formerly infected the network. Copyright (c) 2008 J. R. C. Piqueira and F. B. Cesar. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

FLOWS WITHOUT WANDERING POINTS ON COMPACT CONNECTED SURFACES

Given a compact 2 dimensional manifold M we classify all continuous flows phi without wandering points on M. This classification is performed by finding finitely many pairwise disjoint open phi-invariant subsets {U(1), U(2), ..., U(n)} of M such that U(i=1)(n) (U(i)) over bar = M and each U(i) is either a suspension of an interval exchange transformation, or a maximal open cylinder made up of closed trajectories of phi.

SOME PROPERTIES OF THE MULTIPLICITY SEQUENCE FOR ARBITRARY IDEALS

In this work we prove that the Achilles-Manaresi multiplicity sequence, like the classical Hilbert-Samuel multiplicity, is additive with respect to the exact sequence of modules. We also prove the associativity formula for his mulitplicity sequence. As a consequence, we give new proofs for two results already known. First, the Achilles-Manaresi multiplicity sequence is an invariant up to reduction, a result first proved by Ciuperca. Second, I subset of J is a reduction of (J,M) if and only if c(0)(I(p), M(p)) = c(0)(J(p), M(p)) for all p is an element of Spec(A), a result first proved by Flenner and Manaresi.

LOCAL WELL POSEDNESS, ASYMPTOTIC BEHAVIOR AND ASYMPTOTIC BOOTSTRAPPING FOR A CLASS OF SEMILINEAR EVOLUTION EQUATIONS OF THE SECOND ORDER IN TIME

A class of semilinear evolution equations of the second order in time of the form u(tt)+Au+mu Au(t)+Au(tt) = f(u) is considered, where -A is the Dirichlet Laplacian, 92 is a smooth bounded domain in R(N) and f is an element of C(1) (R, R). A local well posedness result is proved in the Banach spaces W(0)(1,p)(Omega)xW(0)(1,P)(Omega) when f satisfies appropriate critical growth conditions. In the Hilbert setting, if f satisfies all additional dissipativeness condition, the nonlinear Semigroup of global solutions is shown to possess a gradient-like attractor. Existence and regularity of the global attractor are also investigated following the unified semigroup approach, bootstrapping and the interpolation-extrapolation techniques.

Perturbative finiteness of three-dimensional supersymmetric QED to all orders

Within the superfield formalism, we study the ultraviolet properties of the three-dimensional super-symmetric quantum electrodynamics. The theory is shown to be finite at all loop orders in a particular gauge.

An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

On the resilience of long cycles in random graphs

In this paper we determine the local and global resilience of random graphs G(n,p) (p >> n(-1)) with respect to the property of containing a cycle of length at least (1 - alpha)n. Roughly speaking, given alpha > 0, we determine the smallest r(g) (G, alpha) with the property that almost surely every subgraph of G = G(n,p) having more than r(g) (G, alpha)vertical bar E(G)vertical bar edges contains a cycle of length at least (1 - alpha)n (global resilience). We also obtain, for alpha < 1/2, the smallest r(l) (G, alpha) such that any H subset of G having deg(H) (v) larger than r(l) (G, alpha) deg(G) (v) for all v is an element of V(G) contains a cycle of length at least (1 - alpha)n (local resilience). The results above are in fact proved in the more general setting of pseudorandom graphs.

Hitting and returning to rare events for all alpha-mixing processes

We prove that for any a-mixing stationary process the hitting time of any n-string A(n) converges, when suitably normalized, to an exponential law. We identify the normalization constant lambda(A(n)). A similar statement holds also for the return time. To establish this result we prove two other results of independent interest. First, we show a relation between the rescaled hitting time and the rescaled return time, generalizing a theorem of Haydn, Lacroix and Vaienti. Second, we show that for positive entropy systems, the probability of observing any n-string in n consecutive observations goes to zero as n goes to infinity. (c) 2010 Elsevier B.V. All rights reserved.

COMPLETE ISOMORPHIC CLASSIFICATIONS OF SOME SPACES OF COMPACT OPERATORS

This paper is a continuation and a complement of our previous work on isomorphic classification of some spaces of compact operators. We improve the main result concerning extensions of the classical isomorphic classification of the Banach spaces of continuous functions on ordinals. As an application, fixing an ordinal a and denoting by X(xi), omega(alpha) <= xi < omega(alpha+1), the Banach space of all X-valued continuous functions defined in the interval of ordinals [0,xi] and equipped with the supremum, we provide complete isomorphic classifications of some Banach spaces K(X(xi),Y(eta)) of compact operators from X(xi) to Y(eta), eta >= omega. It is relatively consistent with ZFC (Zermelo-Fraenkel set theory with the axiom of choice) that these results include the following cases: 1.X* contains no copy of c(0) and has the Mazur property, and Y = c(0)(J) for every set J. 2. X = c(0)(I) and Y = l(q)(J) for any infinite sets I and J and 1 <= q < infinity. 3. X = l(p)(I) and Y = l(q)(J) for any infinite sets I and J and 1 <= q < p < infinity.

ON ISOMORPHIC CLASSIFICATIONS OF SPACES OF COMPACT OPERATORS

We prove an extension of the classical isomorphic classification of Banach spaces of continuous functions on ordinals. As a consequence, we give complete isomorphic classifications of some Banach spaces K(X,Y(n)), eta >= omega, of compact operators from X to Y(eta), the space of all continuous Y-valued functions defined in the interval of ordinals [1, eta] and equipped with the supremum norm. In particular, under the Continuum Hypothesis, we extend a recent result of C. Samuel by classifying, up to isomorphism, the spaces K(X(xi), c(0)(Gamma)(eta)), where omega <= xi < omega(1,) eta >= omega, Gamma is a countable set, X contains no complemented copy of l(1), X* has the Mazur property and the density character of X** is less than or equal to N(1).