Fast pattern-matching on indeterminate strings

In a string x on an alphabet Σ, a position i is said to be indeterminate iff x[i] may be any one of a specified subset {λ₁,λ₂,…,λ_j} of Σ, 2j|Σ|. A string x containing indeterminate positions is therefore also said to be indeterminate. Indeterminate strings can arise in DNA and amino acid sequences as well as in cryptological applications and the analysis of musical texts. In this paper we describe fast algorithms for finding all occurrences of a pattern p=p[1..m] in a given text x=x[1..n], where either or both of p and x can be indeterminate. Our algorithms are based on the Sunday variant of the Boyer–Moore pattern-matching algorithm, one of the fastest exact pattern-matching algorithms known. The methodology we describe applies more generally to all variants of Boyer–Moore (such as Horspool's, for example) that depend only on calculation of the δ (“rightmost shift”) array: our method therefore assumes that Σ is indexed (essentially, an integer alphabet), a requirement normally satisfied in practice.     

Inversion and canonization of block matrices

The paper is concerned with the problem of inverting block matrices to which the well-known Frobenius— Schur formulas are not applicable. These can be square matrices with four noninvertible square or rectangular blocks as well as square or rectangular matrices with two blocks. With regard to rectangular matrices, the results obtained are a further step in the development of the canonization method, which is used for solving arbitrary matrix equations.     

Short permutation strings

A permutation string is a string of symbols over the numerals 1, 2, …, n such that all permutations of the string 1 2 … n are subsequences. The search for short permutation strings arose out of studies into the complexity of shortest path algorithms by Karp and others. The results in the sequel are presented independent of such studies because they are felt to be of intrinsic combinatorial interest [1]. An algorithm for constructing permutation strings of length n²−2n+4 is given.     

Periods in strings

In this paper we explore the notion of periods of a string. A period can be thought of as a shift that causes the string to match over itself. We obtain two sets of necessary and sufficient conditions for a set of integers to be the set of periods of some string (what we call the correlation of the string). We show that the number of distinct correlations of length n is independent of the alphabet size and is of order n^logn. By using generating function methods we enumerate the strings having a given correlation, and investigate certain related questions.     

Selfgravitating electroweak strings

We obtain selfgravitating multi-string configurations for the Einstein-Weinberg-Salam model, in terms of solutions for a nonlinear elliptic system of Liouville type whose solvability was posed as an open problem in Yang (Solitons in Field Theory and Nonlinear Analysis, Springer, New York, 2001).     

Bit strings withoutq-separation

LetB(n, q) denote the number of bit strings of lengthn withoutq-separation. In a bit string withoutq-separation no two 1's are separated by exactlyq – 1 bits.B(n, q) is known to be expressible in terms of a product of powers of Fibonacci numbers. Two new and independent proofs are given. The first proof is by combinatorial enumeration, while the second proof is inductive and expressesB(n, q) in terms of a recurrence relation.     

Character sets of strings

Given a string S over a finite alphabet Σ, the character set (also called the fingerprint) of a substring S^′ of S is the subset CΣ of the symbols occurring in S^′. The study of the character sets of all the substrings of a given string (or a given collection of strings) appears in several domains such as rule induction for natural language processing or comparative genomics. Several computational problems concerning the character sets of a string arise from these applications, especially:

(1) Output all the maximal locations of substrings having a given character set.

(2) Output for each character set C occurring in a given string (or a given collection of strings) all the maximal locations of C.

Denoting by n the total length of the considered string or collection of strings, we solve the first problem in Θ(n) time using Θ(n) space. We present two algorithms solving the second problem. The first one runs in Θ(n²) time using Θ(n) space. The second algorithm has Θ(n|Σ|log|Σ|) time and Θ(n) space complexity and is an adaptation of an algorithm by Amir et al. [A. Amir, A. Apostolico, G.M. Landau, G. Satta, Efficient text fingerprinting via Parikh mapping, J. Discrete Algorithms 26 (2003) 1–13].     

Eigenvalue ratios of vibrating strings

Summary New results for the eigenvalue ratios of vibrating strings are presented partially in connection with previous results concerning Schr?dinger operators.     

Electrodynamics with charged strings

We show that in a four-dimensional space–time a complex scalar field can be associated with a one-dimensionally extended object, called a charged string. The string is said to be charged because the complex scalar field describing it interacts with an electromagnetic field. A charged string is characterized by an extension of the symmetry group of the charge space to a group of stretch rotations. We propose relativistically invariant and gauge-invariant equations describing the interaction of a complex scalar field with an electromagnetic field, and each solution of them corresponds to a charged string. We achieve this by introducing the notion of a charged string index, which, as verified, takes only integer values. We establish equations from which it follows that charged strings fit naturally into the framework of the Maxwell–Dirac electrodynamics.     

Large strings of consecutive smooth integers

In this note we improve an algorithm from a recent paper by Bauer and Bennett for computing a function of Erdös that measures the minimal gap size f(k) in the sequence of integers at least one of whose prime factors exceeds k. This allows us to compute values of f(k) for larger k and obtain new values of f(k).     

Lyndon-like and V-order factorizations of strings

We say a family of strings is an UMFF if every string has a unique maximal factorization over . Then is an UMFF iff and y non-empty imply . Let L-order denote lexicographic order. Danh and Daykin discovered V-order, B-order and T-order. Let R be L, V, B or T. Then we call r an R-word if it is strictly first in R-order among the cyclic permutations of r. The set of R-words form an UMFF. We show a large class of B-like UMFF. The well-known Lyndon factorization of Chen, Fox and Lyndon is the L case, and it motivated our work.     

Controllability of star-shaped networks of strings

In this note we consider a star-shaped network of vibrating strings. The problem of controllability when one control acts on the junction point is considered. A simple proof is given that, in particular, does not use Ingham inequalities, of the fact that the set of reachable data is dense, whenever the lengths of the strings are mutually irrational. The proof is based on an observability inequality with suitable weights on the Fourier coefficients that is easily obtained as a consequence of the time-periodicity of the solutions. Those weights can be estimated under certain algebraicity conditions imposed on the lengths of the strings. This allows to proof exact controllability results in Sobolev spaces of appropriate order. Further results are also presented concerning the control from a free end and diffusion processes.     

On the structure of run-maximal strings

We present a combinatorial structure consisting of a special cover of a string by squares. We characterize the covering property of run-maximal strings, i.e. strings achieving the maximal number of runs. The covering property leads to a compression scheme which is particularly efficient for run-maximal strings. It also yields a significant speed improvement in the computer search for good run-maximal string candidates. The implementation of the search and preliminary computational results are discussed.