Dirichlet–Neumann inverse spectral problem for a star graph of Stieltjes strings

We solve two inverse spectral problems for star graphs of Stieltjes strings with Dirichlet and Neumann boundary conditions, respectively, at a selected vertex called root. The root is either the central vertex or, in the more challenging problem, a pendant vertex of the star graph. At all other pendant vertices Dirichlet conditions are imposed; at the central vertex, at which a mass may be placed, continuity and Kirchhoff conditions are assumed. We derive conditions on two sets of real numbers to be the spectra of the above Dirichlet and Neumann problems. Our solution for the inverse problems is constructive: we establish algorithms to recover the mass distribution on the star graph (i.e. the point masses and lengths of subintervals between them) from these two spectra and from the lengths of the separate strings. If the root is a pendant vertex, the two spectra uniquely determine the parameters on the main string (i.e. the string incident to the root) if the length of the main string is known. The mass distribution on the other edges need not be unique; the reason for this is the non-uniqueness caused by the non-strict interlacing of the given data in the case when the root is the central vertex. Finally, we relate of our results to tree-patterned matrix inverse problems.     

The Fibonacci code behind super strings and P-Branes. An answer to M. Kaku’s fundamental question

In “Beyond Einstein” the leading string theoretician and notable science writer Michio Kaku referred to what he labelled the ‘strange’ link between the E₈ exceptional Lie group and the various dimensionalities of strings and super string theories and commented on that by saying “If we could understand why the numbers 8, 10 and 26 continually crop up in super string theory, perhaps we could understand why the universe is four dimensional”.In the present work we demonstrate the existence of a Fibonacci code-like connection between the various coupling constants, charges and dimensionalities of super strings and P-Brane theories. This code is based on the Fibonacci numbers and the golden mean and in the final analysis, may be attributed to the deterministically chaotic nature of the hyperbolic Cantorian sets fixing the geometry and topology of quantum spacetime.     

Poincaré families of <Emphasis Type="Italic">G</Emphasis>-bundles on a curve

Let G be a reductive group over an algebraically closed field k. Consider the moduli space of stable principal G-bundles on a smooth projective curve C over k. We give necessary and sufficient conditions for the existence of Poincaré bundles over open subsets of this moduli space, and compute the orders of the corresponding obstruction classes. This generalizes the previous results of Newstead, Ramanan and Balaji–Biswas–Nagaraj–Newstead to all reductive groups, to all topological types of bundles, and also to all characteristics.     

Self-similar p-adic fractal strings and their complex dimensions

We develop a geometric theory of self-similar p-adic fractal strings and their complex dimensions. We obtain a closed-form formula for the geometric zeta functions and show that these zeta functions are rational functions in an appropriate variable. We also prove that every self-similar p-adic fractal string is lattice. Finally, we define the notion of a nonarchimedean self-similar set and discuss its relationship with that of a self-similar p-adic fractal string. We illustrate the general theory by two simple examples, the nonarchimedean Cantor and Fibonacci strings. The text was submitted by the authors in English.     

The consensus string problem for a metric is NP-complete

Given a set S of strings, a consensus string of S based on consensus error is a string w that minimizes the sum of the distances between w and all the strings in S. In this paper, we show that the problem of finding a consensus string based on consensus error is NP-complete when the penalty matrix is a metric.     

Random fractal strings: Their zeta functions, complex dimensions and spectral asymptotics

In this paper a string is a sequence of positive non-increasing real numbers which sums to one. For our purposes a fractal string is a string formed from the lengths of removed sub-intervals created by a recursive decomposition of the unit interval. By using the so-called complex dimensions of the string, the poles of an associated zeta function, it is possible to obtain detailed information about the behaviour of the asymptotic properties of the string. We consider random versions of fractal strings. We show that by using a random recursive self-similar construction, it is possible to obtain similar results to those for deterministic self-similar strings. In the case of strings generated by the excursions of stable subordinators, we show that the complex dimensions can only lie on the real line. The results allow us to discuss the geometric and spectral asymptotics of one-dimensional domains with random fractal boundary.

     

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.     

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.     

Zonotopes whose cellular strings are all coherent

A cellular string of a polytope is a sequence of faces stacked on top of each other in a given direction. The poset of cellular strings, ordered by refinement, is known to be homotopy equivalent to a sphere. The subposet of coherent cellular strings is the face lattice of the fiber polytope, hence is homeomorphic to a sphere. In some special cases, every cellular string is coherent. Such polytopes are said to be all-coherent. We give a complete classification of zonotopes with the all-coherence property in terms of their oriented matroid structure. Although the face lattice of the fiber polytope in this case is not an oriented matroid invariant, we prove that the all-coherence property is invariant.     

A probabilistic analysis of a pattern matching problem

The study and comparison of strings of symbols from a finite or an infinite alphabet is relevant to various areas of science, notably molecular biology, speech recognition, and computer science. In particular, the problem of finding the minimum “distance” between two strings (in general, two blocks of data) is of a practical importance. In this article we investigate the (string) pattern matching problem in a probabilistic framework, namely, it is assumed that both strings form an independent sequences of i.i.d. symbols. Given a text string a of length n and a pattern string b of length m, let M_m,n be the maximum number of matches between b and all m-substrings of a . Our main probabilistic result shows that for a wide range of input parameters in probability (pr.) provided m, n →∞ such that log n = o(m), where P is the probability of a match between any two symbols of these strings, and T is the probability of a match between two positions in the text string and a given position of the pattern string. We also prove that M_m,n/m→P almost surely (a.s.) for log n = o(m). © 1993 John Wiley & Sons. Inc.     

Semi-local String Comparison: Algorithmic Techniques and Applications

Given two strings, the longest common subsequence (LCS) problem consists in computing the length of the longest string that is a subsequence of both input strings. Its generalisation, the all semi-local LCS problem, requires computing the LCS length for each string against all substrings of the other string, and for all prefixes of each string against all suffixes of the other string. We survey a number of algorithmic techniques related to the all semi-local LCS problem. We then present a number of algorithmic applications of these techniques, both existing and new. In particular, we obtain a new all semi-local LCS algorithm, with asymptotic running time matching (in the case of an unbounded alphabet) the fastest known global LCS algorithm by Masek and Paterson. We conclude that semi-local string comparison turns out to be a useful algorithmic plug-in, which unifies, and often improves on, a number of previous approaches to various substring- and subsequence-related problems. The author acknowledges the support of The University of Warwick’s DIMAP (the Centre for Discrete Mathematics and its Applications) during this work.     

The coolest way to generate combinations

We present a practical and elegant method for generating all (s,t)-combinations (binary strings with s zeros and t ones): Identify the shortest prefix ending in 010 or 011 (or the entire string if no such prefix exists), and rotate it by one position to the right. This iterative rule gives an order to (s,t)-combinations that is circular and genlex. Moreover, the rotated portion of the string always contains at most four contiguous runs of zeros and ones, so every iteration can be achieved by transposing at most two pairs of bits. This leads to an efficient loopless and branchless implementation that consists only of two variables and six assignment statements. The order also has a number of striking similarities to colex order, especially its recursive definition and ranking algorithm. In the light of these similarities we have named our order cool-lex!     

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.     

Existence of the uniformly minimum risk equivariant estimators of parameters in a class of normal linear models

In this paper, we study the existence of the uniformly minimum risk equivariant (UMRE) estimators of parameters in a class of normal linear models, which include the normal variance components model, the growth curve model, the extended growth curve model, and the seemingly unrelated regression equations model, and so on. The necessary and sufficient conditions are given for the existence of UMRE estimators of the estimable linear functions of regression coefficients, the covariance matrixV and (trV)^α, where α > 0 is known, in the models under an affine group of transformations for quadratic losses and matrix losses, respectively. Under the (extended) growth curve model and the seemingly unrelated regression equations model, the conclusions given in literature for estimating regression coefficients can be derived by applying the general results in this paper, and the sufficient conditions for non-existence of UMRE estimators ofV and tr(V) are expanded to be necessary and sufficient conditions. In addition, the necessary and sufficient conditions that there exist UMRE estimators of parameters in the variance components model are obtained for the first time.     

Necessary and sufficient existence conditions for a boundary control of vibrations of a string and a spherical layer for small times

We find necessary and sufficient conditions for the existence of a boundary control of vibrations of a string or a spherical layer for critical and subcritical times. We completely analyze the existence of a boundary control of vibrations of a spherical layer by a force on two spheres. We find necessary and sufficient existence conditions for the control. Along with the control problem for vibrations of a spherical layer, we consider a similar control problem for string vibrations.     

Gauged harmonic maps,Born‐Infeld electromagnetism,and magnetic vortices

We study maps from a 2‐surface into the standard 2‐sphere coupled with Born‐Infeld geometric electromagnetism through an Abelian gauge field. Such a formalism extends the classical harmonic map model, known as the σ‐model, governing the spin vector orientation in a ferromagnet allows us to obtain the coexistence of vortices and antivortices characterized by opposite, self‐excited, magnetic flux lines. We show that the Born‐Infeld free parameter may be used to achieve arbitrarily high local concentration of magnetic flux lines that the total minimum energy is an additive function of these quantized flux lines realized as the numbers of vortices antivortices. In the case where the underlying surface, or the domain, is compact, we obtain a necessary sufficient condition for the existence of a unique solution representing a prescribed distribution of vortices antivortices. In the case where the domain is the full plane, we prove the existence of a unique solution representing an arbitrary distribution of vortices and antivortices. Furthermore, we also consider the Einstein gravitation induced by these vortices, known as cosmic strings, establish the existence of a solution representing a prescribed distribution of cosmic strings cosmic antistrings under a necessary sufficient condition that makes the underlying surface a complete surface with respect to the induced gravitational metric. © 2003 Wiley Periodicals, Inc.     

The string merging problem

The string merging problem is to determine a merged string from a given set of strings. The distinguishing property of a solution is that the total cost of editing all of the given strings into this solution is minimal. Necessary and sufficient conditions are presented for the case where this solution matches the solution to the string-to-string correction problem. A special case where deletion is the only allowed edition operation is shown to have the longest common subsequence of the strings as its solution.This research was supported by the U.S. Army Research Office.     

Lambda-fold 2-perfect 6-cycle systems in equipartite graphs

A 6-cycle system of a graph G is an edge-disjoint decomposition of G into 6-cycles. Graphs G, for which necessary and sufficient conditions for existence of a 6-cycle system have been found, include complete graphs and complete equipartite graphs. A 6-cycle system of G is said to be 2-perfect if the graph formed by joining all vertices distance 2 apart in the 6-cycles is again an edge-disjoint decomposition of G, this time into 3-cycles, since the distance 2 graph in any 6-cycle is a pair of disjoint 3-cycles.Necessary and sufficient conditions for existence of 2-perfect 6-cycle systems of both complete graphs and complete equipartite graphs are known, and also of λ-fold complete graphs. In this paper, we complete the problem, giving necessary and sufficient conditions for existence of λ-fold 2-perfect 6-cycle systems of complete equipartite graphs.     

Compact directed acyclic word graphs for a sliding window

Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n denotes the length of w. Larsson achieved an efficient algorithm to maintain suffix trees for a sliding window. It contributes to prediction by partial matching (PPM) style statistical data compression scheme. Compact directed acyclic word graphs (CDAWGs) are a more space-economical data structure for indexing strings. In this paper we propose a linear-time algorithm to maintain CDAWGs for a sliding window.     

A d-dimensional model of the canonical ensemble of open strings

We propose a d-dimensional model of the canonical ensemble of open self-avoiding strings. We consider the model of a solitary open string in the d-dimensional Euclidean space ? ^d, 2 ≤ d < 4, where the string configuration is described by the arc length L and the distance R between string ends. The distribution of the spatial size of the string is determined only by its internal physical state and interaction with the ambient medium. We establish an equation for a transformed probability density W(R,L) of the distance R similar to the known Dyson equation, which is invariant under the continuous group of renormalization transformations; this allows using the renormalization group method to investigate the asymptotic behavior of this density in the case where R→∞ and L→∞. We consider the model of an ensemble of M open strings with the mean string length over the ensemble given by \(\bar L\) , and we use the Darwin-Fowler method to obtain the most probable distribution of strings over their lengths in the limit as M →∞. Averaging the probability density W(R,L) over the canonical ensemble eventually gives the sought density 〈W(R, \(\bar L\) )〉.