On the longest common increasing binary subsequence

Let $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ be two independent sequences of iid Bernoulli random variables with parameter 1/2. Let ${\mathit{LCI}}_n$ be the length of the longest increasing sequence which is a subsequence of both finite sequences $X_1,\dots ,X_n$ and $Y_1,\dots ,Y_n$. We prove that, as n goes to infinity, $n^{?1/2}({\mathit{LCI}}_n?n/2)$ converges in law to a Brownian functional that we identify. To cite this article: C. Houdré et al., C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

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.     

The longest common subsequence problem for arc-annotated sequences

Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The

Full-size image

problem has recently been introduced in [P.A. Evans, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria, 1999; P.A. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99), in: Lecture Notes in Comput. Sci., vol. 1645, 1999, pp. 270–280] as a framework for studying the similarity of arc-annotated sequences. In this paper, we consider arc-annotated sequences with various arc structures and present some new algorithmic and complexity results on the problem. Some of our results answer an open question in [P.A. Evans, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria, 1999; P.A. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99), in: Lecture Notes in Comput. Sci., vol. 1645, 1999, pp. 270–280] and some others improve the hardness results in [P.A. Evans, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria, 1999; P.A. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99), in Lecture Notes in Comput. Sci., vol. 1645, 1999, pp. 270–280].     

Upper bounds for the expected length of a longest common subsequence of two binary sequences

Let f(n) be the expected length of a longest common subsequence of two random binary sequences of length n. It is known that the limit γ = lim_{n→ ∞} n^?1 f(n) exists. Improved upper bounds for γ are given using a new method.     

A concentration bound for the longest increasing subsequence of a randomly chosen involution

In this short note we prove a concentration result for the length of the longest increasing subsequence (LIS) of a randomly and uniformly chosen involution of {1,…,s}.     

The probability that a pair of group elements is autoconjugate

Let g and h be arbitrary elements of a given finite group G. Then g and h are said to be autoconjugate if there exists some automorphism α of G such that h = g^α. In this article, we construct some sharp bounds for the probability that two random elements of G are autoconjugate, denoted by \(\mathcal {P}_{a}(G)\). It is also shown that \(\mathcal {P}_{a}(G)|G|\) depends only on the autoisoclinism class of G.     

On the density of sequences of integers the sum of no two of which is a square II. General sequences

The aim of this paper is to study the maximal density attainable by a sequence S of positive integers having the property that the sum of any two distinct elements of S is never a square. It is shown that there is a constant N₀ such that for all N ? N₀ any set S ? [1, N] having this property must have |S| < 0.475N. The proof uses the Hardy-Littlewood circle method.     

Probability that the commutator of two group elements is equal to a given element

In this paper we study the probability that the commutator of two randomly chosen elements in a finite group is equal to a given element of that group. Explicit computations are obtained for groups G which |G^′| is prime and G^′≤Z(G) as well as for groups G which |G^′| is prime and G^′∩Z(G)=1. This paper extends results of Rusin [see D.J. Rusin, What is the probability that two elements of a finite group commute? Pacific J. Math. 82 (1) (1979) 237-247].     

On stopping points in the plane that lie on a unique optional increasing path

Given a stopping point in the plane, is there an optional increasing path that passes through the stopping point with probability one? The commutation Hypothesis F4 of Cairoli and Walsh was known to be a sufficient condition in continuous time, and we prove that the conditional qualitative independence Hypothesis CQI of Krengel and Sucheston is in fact necessary and sufficient. Rather surprisingly, certain stopping points may lie on a unique optional increasing path, even when the two-parameter nitration is the natural filtration ot a Rrownian sheet. In the construction of these examples, we prove a result of independent interest, namely that the solutions to certain random differentia! equations are optional increasing paths     

Linear maps on operator algebras that preserve elements annihilated by a polynomial

In this paper some purely algebraic results are given concerning linear maps on algebras which preserve elements annihilated by a polynomial of degree greater than 1 and with no repeated roots and applied to linear maps on operator algebras such as standard operator algebras, von Neumann algebras and Banach algebras. Several results are obtained that characterize such linear maps in terms of homomorphisms, anti-homomorphisms, or, at least, Jordan homomorphisms.

     

On the density of sequences of integers the sum of no two of which is a square. I. Arithmetic progressions

The maximal density attainable by a sequence S of positive integers having the property that the sum of any two elements of S is never a square is studied. J. P. Massias exhibited such a sequence with density $\text{11}\text{32}$; it consists of 11 residue classes (mod 32) such that the sum of any two such residue classes is not congruent to a square (mod 32). It is shown that for any positive integer n, one cannot find more than $\text{11}\text{32}\text{n}$ residue classes (mod n) such that the sum of any two is never congruent to a square (mod n). Thus Massias' example has maximal density among those sequences S made up of a finite set of (infinite) arithmetic progressions. A companion paper will bound the maximal density of an arbitrary such sequence S.     

An operator on a Fréchet space with no common invariant subspace with its inverse

A Fréchet space with a two-sided Schauder basis is constructed, such that the corresponding bilateral shift is continuous and invertible, and has no common nontrivial invariant subspace with its inverse. This shows in particular, that the problem of existence of hyperinvariant subspaces for operators on general Fréchet spaces, admits a negative answer. It is also shown that the dual of the Fréchet space constructed can be identified with a commutative locally convex complete topological algebra with unit, which has no closed nontrivial ideals.     

Sequencing jobs that require common resources on a single machine: A solvable case of the TSP

In this paper a one-machine scheduling model is analyzed wheren different jobs are classified intoK groups depending on which additional resource they require. The change-over time from one job to another consists of the removal time or of the set-up time of the two jobs. It is sequence-dependent in the sense that the change-over time is determined by whether or not the two jobs belong to the same group. The objective is to minimize the makespan. This problem can be modeled as an asymmetric Traveling Salesman Problem (TSP) with a specially structured distance matrix. For this problem we give a polynomial time solution algorithm that runs in O(n logn) time. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Development of a miniature robot based on experience that is inspired by nature

In this paper, using nature as inspiration, micro robot is designed. Utilizing the basic principles of the biological systems motion and modern software tools Matlab Simulink and SolidWorks a mathematical analysis and simulation of its mechanism for movement are developed. It will be shown that the Bionics along with use of modern software can be a powerful engineering tool. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Scattering problem for a slowly decreasing potential that is periodically dependent on time

The multidimensional Schrödinger operator with a periodic timedependent potential is considered. The potential may decrease slowly with respect to the space variable and its mean value with respect to time is equal to zero. It is shown that for the pair H₀=?Δ, H, there exist wave operators, and their ranges coincide with the absolutely continuous subspace of the corresponding monodromy operator.     

Criterion for testing the hypothesis that a distribution belong to a family of functions with intensity of failures increasing on average for a small sample

A statistical criterion based on properties of order statistics generated by continuous distributions is considered which from a limited number of observations lets one test the hypothesis that an unknown distribution belongs to a family of functions with intensity of failures increasing on average.Translated from Statisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 88–92, 1988.