Extracting approximate patterns

In this paper, we define a family of patterns with don't cares occurring in a text. We call them primitive patterns. The set of primitive patterns forms a basis for all the maximal patterns occurring in the text. The number of primitive patterns is smaller than other known basis.

We present an incremental algorithm that computes the primitive patterns occurring at least q times in a text of length n, given the N primitive patterns occurring at least q−1 times, in time O(|Σ|Nn²logn), where Σ is the alphabet. In the particular case where q=2, the complexity in time is only O(|Σ|n²logn). We also give an algorithm that decides if a given pattern is primitive in a given text. These algorithms are generalized, taking many sequences in input. Finally, we give a solution for reducing the number of patterns of interest by using scoring techniques, as we show that the number of primitive patterns is exponential.     

Generalizing the Quinn–Wójs theorem on distinct multiplets of composite Fermions

The combinatorial tool of generating functions for restricted partitions is used to generalize a quantum physics theorem relating distinct multiplets of different angular momenta in the composite Fermion model of the fractional quantum Hall effect. Specifically, if g_ℓ(N,M) denotes the number of distinct multiplets of angular momentum ℓ and total angular momentum M, we prove that

where the sum is taken over all positive divisors of N and L(k)=kℓ-kN/2+3k/2-N+N/(2k)-1/2. The original Quinn–Wójs theorem results when k=1 and it appears that this generalization will be useful in further investigations of nuclear shells modeling elementary particle interactions when the particles are clustered together.     

Visibility maps of segments and triangles in 3D

Let T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the subdivision of T based on (in)visibility from s; this is the visibility map of the segment s with respect to T. The visibility map of the triangle t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(n²) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n²(n)) upper bound for both structures, where (n) is the extremely slowly increasing inverse Ackermann function. Furthermore, we prove that the weak visibility map of s has complexity Θ(n⁵), and the weak visibility map of t has complexity Θ(n⁷). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n⁴) and O(n⁵), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.     

Diameter preserving surjections in the geometry of matrices

We consider a class of graphs subject to certain restrictions, including the finiteness of diameters. Any surjective mapping φ:Γ→Γ^′ between graphs from this class is shown to be an isomorphism provided that the following holds: Any two points of Γ are at a distance equal to the diameter of Γ if, and only if, their images are at a distance equal to the diameter of Γ^′. This result is then applied to the graphs arising from the adjacency relations of spaces of rectangular matrices, spaces of Hermitian matrices, and Grassmann spaces (projective spaces of rectangular matrices).     

On four color monochromatic sets with nondecreasing diameter

Let m and r be positive integers. Define f(m,r) to be the least positive integer N such that for every coloring of the integers 1,…,N with r colors there exist monochromatic subsets B₁ and B₂ (not necessarily of the same color), each having m elements, such that (a) max(B₁)-min(B₁)max(B₂)-min(B₂), and (b) max(B₁)B₂). We improve previous upper bounds to determine that f(m,4)=12m-9.     

A note on an unusual type of polar decomposition

Motivated by applications in the theory of unitary congruence, we introduce the factorization of a square complex matrix A of the form A=SU, where S is complex symmetric and U is unitary. We call this factorization a symmetric–unitary polar decomposition or an SUPD. It is shown that an SUPD exists for every matrix A and is always nonunique. Even the symmetric factor S can be chosen in infinitely many ways. Nevertheless, we show that many properties of the conventional polar decomposition related to normal matrices have their counterparts for the SUPD, provided that normal matrices are replaced with conjugate–normal ones.     

Matrices with convolutions of binomial functions and Krawtchouk matrices

We introduce a class S_N of matrices whose elements are terms of convolutions of binomial functions of complex numbers. A multiplication theorem is proved for elements of S_N. The multiplication theorem establishes a homomorphism of the group of 2 by 2 nonsingular matrices with complex elements into a group G_N contained in S_N. As a direct consequence of representation theory, we also present related spectral representations for special members of G_N. We show that a subset of G_N constitutes the system of Krawtchouk matrices, which extends published results for the symmetric case.     

On computing of arbitrary positive integer powers for one type of even order tridiagonal matrices with eigenvalues on imaginary axis – II

This paper is an extension of the work [J. Rimas, On computing of arbitrary positive integer powers for one type of even order tridiagonal matrices with eigenvalues on imaginary axis – I, Appl. Math. Comput., in press] in which the general expression of the lth power (lN) for one type of even order tridiagonal matrices is given. In this new paper we present the complete derivation of this general expression. Expressions of eigenvectors of the matrix and of the transforming matrix and its inverse are given, too.     

2-Tree probe interval graphs have a large obstruction set

Probe interval graphs (PIGs) are used as a generalization of interval graphs in physical mapping of DNA. G=(V,E) is a probe interval graph (PIG) with respect to a partition (P,N) of V if vertices of G correspond to intervals on a real line and two vertices are adjacent if and only if their corresponding intervals intersect and at least one of them is in P; vertices belonging to P are called probes and vertices belonging to N are called non-probes. One common approach to studying the structure of a new family of graphs is to determine if there is a concise family of forbidden induced subgraphs. It has been shown that there are two forbidden induced subgraphs that characterize tree PIGs. In this paper we show that having a concise forbidden induced subgraph characterization does not extend to 2-tree PIGs; in particular, we show that there are at least 62 minimal forbidden induced subgraphs for 2-tree PIGs.     

Proximity problems on line segments spanned by points

Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O(nlogn) time, O(n) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S{q} in optimal O(nlogn) time and O(n) space. Finally, we give an O(nlogn) time, O(n) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O(nlogn+k) time and O(n+k) space.     

Constructing suffix arrays in linear time

The time complexity of suffix tree construction has been shown to be equivalent to that of sorting: O(n) for a constant-size alphabet or an integer alphabet and O(nlogn) for a general alphabet. However, previous algorithms for constructing suffix arrays have the time complexity of O(nlogn) even for a constant-size alphabet.

In this paper we present a linear-time algorithm to construct suffix arrays for integer alphabets, which do not use suffix trees as intermediate data structures during its construction. Since the case of a constant-size alphabet can be subsumed in that of an integer alphabet, our result implies that the time complexity of directly constructing suffix arrays matches that of constructing suffix trees.     

Bit-parallel approximate string matching algorithms with transposition

Using bit-parallelism has resulted in fast and practical algorithms for approximate string matching under Levenshtein edit distance, which permits a single edit operation to insert, delete or substitute a character. Depending on the parameters of the search, currently the fastest non-filtering algorithms in practice are the O(km/wn) algorithm of Wu and Manber, the O((k+2)(m−k)/wn) algorithm of Baeza-Yates and Navarro, and the O(m/wn) algorithm of Myers, where m is the pattern length, n is the text length, k is the error threshold and w is the computer word size. In this paper we discuss a uniform way of modifying each of these algorithms to permit also a fourth type of edit operation: transposing two adjacent characters in the pattern. This type of edit distance is also known as Damerau edit distance. In the end we also present an experimental comparison of the resulting algorithms.     

Edge-coloring of multigraphs

We introduce a monotone invariant π(G) on graphs and show that it is an upper bound of the chromatic index of graphs. Moreover, there exist polynomial time algorithms for computing π(G) and for coloring edges of a multigraph G by π(G) colors. This generalizes the classical edge-coloring theorems of Shannon and Vizing.     

On -differential graded algebras

We introduce the concept of N-differential graded algebras (N-dga), and study the moduli space of deformations of the differential of an N-dga. We prove that it is controlled by what we call the (M,N)-Maurer–Cartan equation.     

Chaining algorithms for multiple genome comparison

Given n fragments from k>2 genomes, Myers and Miller showed how to find an optimal global chain of colinear non-overlapping fragments in O(nlog^kn) time and O(nlog^k−1n) space. For gap costs in the L₁-metric, we reduce the time complexity of their algorithm by a factor and the space complexity by a factor logn. For the sum-of-pairs gap cost, our algorithm improves the time complexity of their algorithm by a factor . A variant of our algorithm finds all significant local chains of colinear non-overlapping fragments. These chaining algorithms can be used in a variety of problems in comparative genomics: the computation of global alignments of complete genomes, the identification of regions of similarity (candidate regions of conserved synteny), the detection of genome rearrangements, and exon prediction.     

Ore-type degree condition for heavy paths in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident to v. And the weight of a path is the sum of the weights of the edges belonging to it. In this paper, we give a sufficient condition for a weighted graph to have a heavy path which joins two specified vertices. Let G be a 2-connected weighted graph and let x and y be distinct vertices of G. Suppose that d^w(u)+d^w(v)2d for every pair of non-adjacent vertices u and vV(G) x,y . Then x and y are joined by a path of weight at least d, or they are joined by a Hamilton path. Also, we consider the case when G has some vertices whose weighted degree are not assumed.     

A combinatorial approach to doubly transitive permutation groups

Let G be a doubly but not triply transitive group on a set X. We give an algorithm to construct the orbits of G acting on X×X×X by combining those of its stabilizer H of a point of X If the group H is given first, we compute the orbits of its transitive extension G, if it exists. We apply our algorithm to G=PSL(m,q) and Sp(2m,2), m3, successfully. We go forward to compute the transitive extension of G itself. In our construction we use a superscheme defined by the orbits of H on X×X×X and do not use group elements.     

An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

We consider the asymmetric traveling salesperson problem with γ-parameterized triangle inequality for γ[1/2,1). That means, the edge weights fulfill w(u,v)γ(w(u,x)+w(x,v)) for all nodes u,v,x. Chandran and Ram [L.S. Chandran, L.S. Ram, Approximations for ATSP with parametrized triangle inequality, in: Proc. 19th Int. Symp. on Theoret. Aspects of Comput. Sci. (STACS), in: Lecture Notes in Comput. Sci., vol. 2285, Springer, Berlin, 2002, pp. 227–237] gave the first constant factor approximation algorithm with polynomial running time for this problem. They achieve performance ratio γ/(1−γ). We devise an approximation algorithm with performance ratio (1+γ)/(2−γ−γ³), which is better for γ[0.5437,1), that is, for the particularly interesting large values of γ.     

Computing homotopic shortest paths efficiently

We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time , and the randomized algorithm runs in expected time O(k_out+k_inlogn+n(logn)^1+ε). Here k_in is the number of edges in all the paths of Π, and k_out is the number of edges in the output paths.     

Cauchy–Riemann equations and J-symplectic forms

Let (Σ,j) be a Riemann surface. The almost complex manifolds (M,J) for which the J-holomorphic curves :Σ→M are of variational type, are characterized. This problem is related to the existence of a vertically non-degenerate closed complex 3-form on Σ×M (see Theorem 4.3 below), which determines a family of J-symplectic structures on (M,J) parametrized by Σ.