Narrow Results

Computing approximate patterns in strings or sequences has important applications in DNA sequence analysis, data compression, musical text analysis, and so on. In this paper, we introduce approximate k-covers and study them under various commonly used distance measures. We propose the following problem: "Given a string x of length n, a set U of m strings of length k, and a distance measure, compute the minimum number t such that U is a set of approximate k-covers for x with distance t". To solve this problem, we present three algorithms with time complexity O(km(n - k)), O(mn²) and O(mn²) under Hamming, Levenshtein and edit distance, respectively. A World Wide Web server interface has been established at for automated use of the programs.

The purpose of this paper is to present various algebraic views of multisets, and certain connections between the theory of multisets (with multiplicities in the semiring of positive integers) and natural computing, in particular membrane and DNA computing. We introduce a Gödel encoding of multisets, and find some results regarding this encoding together with new connections and interpretations. We also introduce the norm of a multiset and we find some relationships between multiset theory and number theory.

Abelian periodicity of strings has been studied extensively over the last years. In 2006 Constantinescu and Ilie defined the abelian period of a string and several algorithms for the computation of all abelian periods of a string were given. In contrast to the classical period of a word, its abelian version is more flexible, factors of the word are considered the same under any internal permutation of their letters. We show two O(|y|²) algorithms for the computation of all abelian periods of a string y. The first one maps each letter to a suitable number such that each factor of the string can be identified by the unique sum of the numbers corresponding to its letters and hence abelian periods can be identified easily. The other one maps each letter to a prime number such that each factor of the string can be identified by the unique product of the numbers corresponding to its letters and so abelian periods can be identified easily. We also define weak abelian periods on strings and give an O(|y|log(|y|)) algorithm for their computation, together with some other algorithms for more basic problems.

This paper presents a parallel algorithm for verifying that a string X is formed by the shuffle of two strings Y and Z. The algorithm runs in O(log²n) time with O(n²/log² n) processors on the EREW-PRAM model.