Search

A string T of length m is periodic in P of length p if P is a substring of T and T [ i ] = T [ i + p ] for all 0 ≤ i ≤ m − p − 1 and m ≥ 2 p . The shortest such prefix, P , is called the period of T (i.e., P = T [ 0 . . p − 1 ] ). In this paper we investigate the period recovery problem. Given a string S of length n , find the primitive period(s) P such that the distance between S and a string T that is periodic in P is below a threshold τ . We consider the period recovery problem over both the Hamming distance and the edit distance. For the Hamming distance case, we present an O ( n log ⁡ n ) -time algorithm, where τ is given as ⌊ n ( 2 + ϵ ) p ⌋ , for ϵ > 0 . For the edit distance case, τ = ⌊ n ( 3.75 + ϵ ) p ⌋ and ϵ > 0 , we provide an O ( n 4 / 3 ) -time algorithm. [ABSTRACT FROM AUTHOR]

Two symmetrical fractional factorial designs are said to be combinatorially equivalent if one design can be obtained from another by reordering the runs, relabeling the factors and relabeling the levels of one or more factors. This article presents concepts of ordered distance frequency matrix, distance frequency vector, and reduced distance frequency vector for a design. Necessary conditions for two designs to be combinatorial equivalent based on these concepts are presented. A new algorithm based on the results obtained is proposed to check combinatorial non-equivalence of two factorial designs and several illustrating examples are provided. [ABSTRACT FROM AUTHOR]

Pick a binary string of length n and remove its first bit b. Now insert b after the first remaining 10, or insert $\overline{b}$ at the end if there is no remaining 10. Do it again. And again. Keep going! Eventually, you will cycle through all 2 of the binary strings of length n. For example, [InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.] are the binary strings of length n=4, where [InlineEquation not available: see fulltext.] and [InlineEquation not available: see fulltext.]. And if you only want strings with weight (number of 1s) between ℓ and u? Just insert b instead of $\overline{b}$ when the result would have too many 1s or too few 1s. For example, [InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.] are the strings with n=4, ℓ=0 and u=2. This generalizes 'cool-lex' order by Ruskey and Williams ( The coolest way to generate combinations, Discrete Mathematics) and we present two applications of our 'cooler' order. First, we give a loopless algorithm for generating binary strings with any weight range in which successive strings have Levenshtein distance two. Second, we construct de Bruijn sequences for (i) ℓ=0 and any u (maximum specified weight), (ii) any ℓ and u= n (minimum specified weight), and (iii) odd u− ℓ (even size weight range). For example, all binary strings with n=6, ℓ=1, and u=4 appear once (cyclically) in [InlineEquation not available: see fulltext.]. We also investigate the recursive structure of our order and show that it shares certain sublist properties with lexicographic order. [ABSTRACT FROM AUTHOR]

Given an alphabet Σ={1,2,...,|Σ|} text string T∈Σ and a pattern string P∈Σ, for each i=1,2,..., n− m+1 define L( i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L distance is to compute L( i) for every i=1,2,..., n− m+1. We discuss the problem for d=1,2,∞. First, in the case of L matching (pattern matching with an L distance) we show a reduction of the string matching with mismatches problem to the L matching problem and we present an algorithm that approximates the L matching up to a factor of 1+ ε, which has an $O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|)$ run time. Then, the L matching problem (pattern matching with an L distance) is solved with a simple O( nlog m) time algorithm. Finally, we provide an algorithm that approximates the L matching up to a factor of 1+ ε with a run time of $O(\frac{1}{\varepsilon}n\log m\log|\Sigma|)$ . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O( nlog m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric. [ABSTRACT FROM AUTHOR]

Distance-increasing maps from binary vectors to permutations, namely DIMs, are useful for the construction of permutation arrays. While a simple mapping algorithm defining DIMs of even lengths is known, existing DIMs of odd lengths are defined either by recursively merging DIMs of shorter lengths or by complicated mapping algorithms. In this paper, simple mapping algorithms defining DIMs of all lengths are presented. [ABSTRACT FROM AUTHOR]