Improved Approximate String Matching Using Compressed Suffix Data Structures

Approximate string matching is about finding a given string pattern in a text by allowing some degree of errors. In this paper we present a space efficient data structure to solve the 1-mismatch and 1-difference problems. Given a text T of length n over an alphabet A, we can preprocess T and give an -bit space data structure so that, for any query pattern P of length m, we can find all 1-mismatch (or 1-difference) occurrences of P in O(|A|mlog log n+occ) time, where occ is the number of occurrences. This is the fastest known query time given that the space of the data structure is o(nlog ² n) bits. The space of our data structure can be further reduced to O(nlog |A|) with the query time increasing by a factor of log  ^ε n, for 0<ε≤1. Furthermore, our solution can be generalized to solve the k-mismatch (and the k-difference) problem in O(|A| ^k m ^k (k+log log n)+occ) and O(log  ^ε n(|A| ^k m ^k (k+log log n)+occ)) time using an -bit and an O(nlog |A|)-bit indexing data structures, respectively. We assume that the alphabet size |A| is bounded by for the -bit space data structure.     

On circular-L(2, 1)-labellings of products of graphs

Let m, j and k be positive integers. An m-circular-L(j, k)-labelling of a graph G is an assignment f from { 0, 1,?…?, m?1} to the vertices of G such that, for any two vertices u and v, |f(u)?f(v)|_m≥j if uv∈E(G), and |f(u)?f(v)|_m≥k if d_G(u, v)=2, where |a|_m=min{a, m?a}. The minimum m such that G has an m-circular-L(j, k)-labelling is called the circular-L(j, k)-labelling number of G. This paper determines the circular-L(2, 1)-labelling numbers of the direct product of a path and a complete graph and of the Cartesian product of a path and a cycle.     

A universal topological transformation group inL 2 (G × G)

LetG denote an infinite,-compact, locally compact topological group. In this paper a construction is given for a topological transformation groupH _G with the Hilbert spaceL ² (G × G) as a phase space such that any topological transformation group (G, X, ) can be embedded inH _G , providedX is a separable metrizable space and is a bounded action. The class of such topological transformation groups contains all actions ofG on separable, metrizable, locally compact spaces.     

On closed-form approximations for the free energy ofd-dimensional Ising model,II

It has been shown that it is possible to construct families of closed-form approximations lnZ* _d to lnZ _d for the anisotropic Ising model on ad-dimensional hypercubical lattice whose high- and low-temperature series expansions coincide with the corresponding exact expansions up to some order. For the isotropic case the density of zeros ofZ* _d near the critical pointK _c is found under the assumption that they behave like sinh2K=±(sinh2K _c +y±iy). It is shown that there exists a family of closed-form approximations such that ford3 the only possible densities of zeros arem(y)=|y|³ for=0 andm(y)=|y| for 0<||1, i.e., it contains the exact case ford5 corresponding to ||=1.     

Robust stabilization of infinite dimensional systems by finite dimensional controllers

The problem of robustly stabilizing an infinite dimensional system with transfer function G, subject to an additive perturbation Δ is considered. It is assumed that: G ε ₀(σ) of systems introduced by Callier and Desoer [3]; the perturbation satisfies |W₁ΔW₂| < ε, where W₁ and W₂ are stable and minimum phase; and G and G + Δ have the same number of poles in ⁺. Now write W₁GW₂=G₁ + G₁, where G₁ is rational and totally unstable and G₂ is stable. Generalizing the finite dimensional results of Glover [12] this family of perturbed systems is shown to be stabilizable if and only if ε σ_min (G^*₁)( = the smallest Hankel singular value of G^*₁). A finite dimensional stabilizing controller is then given by where 2 is a rational approximation of G₂ such that

Full-size image

) and K₁ robustly stabilizes G₁ to margin ε. The feedback system (G, K) will then be stable if |W₁ΔW₂| _∞< ε − Δ.     

Asynchronous deterministic rendezvous in graphs

Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting, meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance D   in an infinite line, we show a rendezvous algorithm with cost O(D|_Lmin|²)$\mathrm{O}(D|L_{\min }{|}^2)$ when D   is known and O((D+|_Lmax|)³)$\mathrm{O}((D+\left|L_{\max }\right|{)}^3)$ if D   is unknown, where |_Lmin|$\left|L_{\min }\right|$ and |_Lmax|$\left|L_{\max }\right|$ are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size, but then we also give an optimal algorithm of cost O(n|_Lmin|)$\mathrm{O}(n|L_{\min }|)$, if the size n   of the ring is known, and of cost O(n|_Lmax|)$\mathrm{O}(n|L_{\max }|)$, if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O(D|_Lmin|)$\mathrm{O}(D|L_{\min }|)$ if the topology of the graph and the initial positions are known to agents.     

On the equivalence and containment problems for context-free languages

LetG andG ₀ be context-free grammars. Necessary and sufficient conditions onG ₀ are obtained for the decidability ofL(G ₀) L((G) It is also shown that it is undecidable for whichG ₀,L(G) is decidable. Furthermore, given thatL(G) is decidable for a fixedG ₀, there is no effective procedure to determine the algorithm which decidesL(G) IfL(G ₀) is a regular set,L(G) = L(G ₀) is decidable if and only ifL(G ₀) is bounded. However, there exist non-regular, unboundedL(G ₀) for whichL(G) = L(G ₀) is decidable.     

A fast distributed approximation algorithm for minimum spanning trees

We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time Õ(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any $H\,\in\,[1, \Theta({\rm log} n)]We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time ?(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any . Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal ?(D(G)) time.     

Minimization of the maximal lateness for a single machine

Consideration was given to the classical NP-hard problem 1|r_j|L_max of the scheduling theory. An algorithm to determine the optimal schedule of processing n jobs where the job parameters satisfy a system of linear constraints was presented. The polynomially solvable area of the problem 1|r_j|L_max was expanded. An algorithm was described to construct a Pareto-optimal set of schedules by the criteria L_max and C_max for complexity of O(n³logn) operations.     

How to Steer a Quantum System over a Schrödinger Bridge

A new approach to the steering problem for the Schrödinger equation relying on stochastic mechanics and on the theory of Schrödinger bridges is presented. Given the initial and final states ₀ and ₁, respectively, the desired quantum evolution is constructed with the aid of a reference quantum evolution. The Nelson process corresponding to the latter evolution is used as reference process in a Schrödinger bridge problem with marginal probability densities | ₀|² and | ₁|². This approach is illustrated by working out a simple Gaussian example. PACS: 03.65.-w     

Information entropy,rough entropy and knowledge granulation in incomplete information systems

Rough set theory is a relatively new mathematical tool for use in computer applications in circumstances that are characterized by vagueness and uncertainty. Rough set theory uses a table called an information system, and knowledge is defined as classifications of an information system. In this paper, we introduce the concepts of information entropy, rough entropy, knowledge granulation and granularity measure in incomplete information systems, their important properties are given, and the relationships among these concepts are established. The relationship between the information entropy E(A) and the knowledge granulation GK(A) of knowledge A can be expressed as E(A)+GK(A) = 1, the relationship between the granularity measure G(A) and the rough entropy E _r(A) of knowledge A can be expressed as G(A)+E _r(A) = log₂|U|. The conclusions in Liang and Shi (2004 Liang, J.Y. and Shi, Z.Z. 2004. The information entropy, rough entropy and knowledge granulation in rough set theory. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 12(1): 37–46. [Crossref], [Web of Science ®] , [Google Scholar]) are special instances in this paper. Furthermore, two inequalities ? log₂ GK(A) ≤ G(A) and E _r(A) ≤ log₂(|U|(1 ? E(A))) about the measures GK, G, E and E _r are obtained. These results will be very helpful for understanding the essence of uncertainty measurement, the significance of an attribute, constructing the heuristic function in a heuristic reduct algorithm and measuring the quality of a decision rule in incomplete information systems.     

A forbidden subposet characterization of an order — dimension inequality

Dushnik and Miller defined the dimension of a partially ordered setX, DimX, as the minimum number of linear extensions ofX whose intersection is the partial ordering onX. The concept of dimension for a partially ordered set has applications to preference structures and the theory of measurement. Hiraguchi proved that DimX [|X|/2] when |X| 4. Bogart, Trotter, and Kimble gave a forbidden subposet characterization of Hiraguchi's inequality by constructing for eachn 2 the minimum collection _n of posets such that if [|X|/2] =n 2, then DimX < n unlessX contains one of the posets in _n . Recently Trotter gave a simple proof of Hiraguchi's inequality based on the following theorem. IfA is an antichain ofX and |X – A| =n 2, then DimX n. In this paper we give a forbidden subposet characterization of this last inequality.     

Human frequency characteristics in manual tracking of three input waves

Abstract

The experimental task was manual tracking. The parameters studied were input wave forms. The wave forms used were a step wave, a sinusoidal wave, and a random wave. Human responses to a step wave are typically described in a time domain as O_a (t). But they can also be described in a frequency domain as G ₁(jω) by Fourier transform:

Human responses to sinusoidal waves of various frequencies with their amplitude held constant are described in a frequency domain as G ₂(jω). Responses to a random wave consisting of superposed and filtered sinusoidal waves are similarly described in a frequency domain as G ₃(jω). Frequency characteristics of human responses to the three input waves were similar in shape, but somewhat reflected the characteristics of each input. From these frequency characteristics, called closed-loop characteristics and referred to as G(jω), open-loop characteristics of H(jω) may be calculated by the following equation:

In classical control theories it is conventional to evaluate a system on the basis of the three indices of rapidity, stability and control performance, human responses to the three input waves as observed in the laboratory will be discussed in terms of three indices.     

On finite groups with large degrees of irreducible character

Let G be a finite nontrivial group with an irreducible complex character χ of degree d = χ(1). According to the orthogonality relation, the sum of the squared degrees of irreducible characters of G is the order of G. N. Snyder proved that, if G = d(d + e), then the order of the group G is bounded in terms of e for e > 1. Y. Berkovich demonstrated that, in the case e = 1, the group G is Frobenius with the complement of order d. This paper studies a finite nontrivial group G with an irreducible complex character Θ such that G ≤ 2Θ(1)² and Θ(1) = pq where p and q are different primes. In this case, we have shown that G is a solvable group with an Abelian normal subgroup K of index pq. Using the classification of finite simple groups, we have established that the simple non-Abelian group, the order of which is divisible by the prime p and not greater than 2p ⁴ is isomorphic to one of the following groups: L ₂(q), L ₃(q), U ₃(q), S _z(8), A ₇, M ₁₁, and J ₁.     

A simplified approach for the design of basically non-interacting multiple-input-multiple-output systems using qft

Quantitative feedback theory (QFT) has presented techniques for the design of multiple-input-multiple-output (MIMO) linear time invariant (LTI) systems with structured parameter uncertainty in the plant P for the satisfaction of specifications on the closed loop transfer function matrix T = [T_ij]. In many practical applications the specifications are of the basically non-interacting (BNIA) type, i.e. a_ii(ω) < | T_ii(jω) | < b_ii(ω), | T_ij(jω) | < b_ij(ω), (i ≠ j) and b_ij(ω) < a_ii(ω) in a significant range of frequencies. In one QFT technique the design is based on expressing when the matrix of compensators G = diag(G_ii(s)), L_i = G_iiQ_ii, P^?1 = [1/Q_ij], D_ij a disturbance due to plant interaction between the different system channels. It is shown in this paper that when the specifications are BNIA and F = diag(F_ii(s)), the effect of the disturbance acting on the main diagonal terms (i.e. D_ii) can be neglected. This observation saves some computational burden because satisfaction of specifications on the T_iis becomes a single-input-single-output (SISO) design problem instead of the more elaborated multiple-input-single-output (MISO) design problem which had to be designed originally. A detailed 2-input-2-output design example is presented illustrating the simpler approach, stressing the importance of considering the correlation between specifications in the design procedure.     

A Neural Algorithm for the Maximum Clique Problem: Analysis,Experiments, and Circuit Implementation

{In this paper we design and analyze a neural approximation algorithm for the Maximum Clique problem. This algorithm, having as input an arbitrary undirected graph G = \langle V, E\rangle , constructs a finite sequence of Hopfield networks such that the attractor of the last network in the sequence represents a maximal clique of G . We prove that D(G) ⋅ |E ^{\rm c} | , where D(G) = max _{{i,j}\notin E} \min{d _i , d _j } , d _i is the degree of the vertex i of G , and |E ^{\rm c} | denotes the cardinality of the set of edges in the complement graph, is an upper bound to the number of the networks in the sequence. Some experiments made on the second DIMACS benchmark and on random graphs show that: 1. The quality of the solutions found by the algorithm is satisfactory. 2. The theoretical upper bound D(G) ⋅ |E ^{\rm c} | is quite pessimistic. For random graphs we propose an empirical formula that gives a better estimate of the number of networks in the sequence. Moreover, thanks to the simplicity of the algorithm, we are able to design a uniform family of circuits of small size (\approx 10n ² log ₂ n ) that implements it. The circuit, which solves the problems for graphs of at most 32 vertices, has then been programmed on FPGAs (Field Programmable Gate Arrays). An analysis in terms of size and time complexity is given. Received November 10, 1998; revised December 2000.     

Systems of Strings with High Mutual Complexity

Consider a binary string x ₀ of Kolmogorov complexity K(x ₀) n. The question is whether there exist two strings x ₁ and x ₂ such that the approximate equalities K(x _i x _j ) n and K(x _i x _j , x _k ) n hold for all 0 i, j, k 2, i j k, i k. We prove that the answer is positive if we require the equalities to hold up to an additive term O(log K(x ₀)). It becomes negative in the case of better accuracy, namely, O(log n).     

A Note on Decision versus Search for Graph Automorphism

We show that for any graphG,knontrivial automorphisms ofG—if as many exist—can be computed in time |G|^{O(log k)}with nonadaptive queries to GA, the decision problem for Graph Automorphism. As a consequence, we show that some problems related to GA are actually polynomial-time truth-table equivalent to GA. One of these results provides an answer to an open question of Lubiw [SIAM J. Comput.10(1981), 11–21].