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.     

Strong characterizing sequences for subgroups of compact groups

In [A. Biró, V.T. Sós, Strong characterizing sequences in simultaneous Diophantine approximation, J. Number Theory 99 (2003) 405–414] we proved that if Γ is a subgroup of the torus R/Z generated by finitely many independent irrationals, then there is an infinite subset AZ which characterizes Γ in the sense that for γR/Z we have ∑_aAaγ<∞ if and only if γΓ. Here we consider a general compact metrizable Abelian group G instead of R/Z, and we characterize its finitely generated free subgroups Γ by subsets AG^*, where G^* is the Pontriagin dual of G. For this case we prove stronger forms of the analogue of the theorem of the above mentioned work, and we find necessary and sufficient conditions for a kind of strengthening of this statement to be true.     

Homology of Newtonian Coalgebras

Given a Newtonian coalgebra we associate to it a chain complex. The homology groups of this Newtonian chain complex are computed for two important Newtonian coalgebras arising in the study of flag vectors of polytopes:R a, b and Rc, d. The homology of Ra, b corresponds to the homology of the boundary of then -crosspolytope. In contrast, the homology of Rc, d depends on the characteristic of the underlying ring R. In the case the ring has characteristic 2, the homology is computed via cubical complexes arising from distributive lattices. This paper ends with a characterization of the integer homology ofZ c, d.     

Universal Polynomial Majorants on Convex Bodies

Let K be a convex body in ^d (d2), and denote by B_n(K) the set of all polynomials p_n in ^d of total degree n such that |p_n|1 on K. In this paper we consider the following question: does there exist a p*_nB_n(K) which majorates every element of B_n(K) outside of K? In other words can we find a minimal γ1 and p*_nB_n(K) so that |p_n(x)|γ |p*_n(x)| for every p_nB_n(K) and x ^d\K? We discuss the magnitude of γ and construct the universal majorants p*_n for evenn. It is shown that γ can be 1 only on ellipsoids. Moreover, γ=O(1) on polytopes and has at most polynomial growth with respect to n, in general, for every convex body K.     

Some Remarks on “Language-Created Entities”

Some entities, such as fictional characters, propositions, properties, events and numbers are prima facie promising candidates for owing their existence to our linguistic and conceptual practices. However, it is notoriously hard to pin down just what sets such allegedly “language-created” entities apart from ordinary entities. The present paper considers some of the features that are supposed to distinguish between entities of the two kinds and argues that, on an independently plausible account of what it takes to individuate objects, the criteria let in more than friends of the strategy might be happy with.

Independence Distribution Preserving Covariance Structures for the Multivariate Linear Model

Consider the multivariate linear model for the random matrixY_n×pMN(XB, VΣ), whereBis the parameter matrix,Xis a model matrix, not necessarily of full rank, andVΣ is annp×nppositive-definite dispersion matrix. This paper presents sufficient conditions on the positive-definite matrixVsuch that the statistics for testingH₀: CB=0vsH_a: CB≠0have the same distribution as under the i.i.d. covariance structureIΣ.     

Dimension in diffeology

We define the dimension function for diffeological spaces, a simple but new invariant. We show then how it can be applied to prove that, for two different integers m and n the quotient spaces R^m/O(m) and Rⁿ/O(n) are not diffeomorphic, and not diffeomorphic to the half-line [0, ∞[ R.     

A Nonsymmetric Correlation Inequality for Gaussian Measure

Letμbe a Gaussian measure (say, onRⁿ) and letK,LRⁿbe such thatKis convex,Lis a “layer” (i.e.,L={x: ax, ub} for somea, bRanduRⁿ), and the centers of mass (with respect toμ) ofKandLcoincide. Thenμ(K∩L)μ(K)·μ(L). This is motivated by the well-known “positive correlation conjecture” for symmetric sets and a related inequality of Sidak concerning confidence regions for means of multivariate normal distributions. The proof uses the estimateΦ(x)> 1−((8/π)^1/2/(3x+(x²+8)^1/2))e^−x2/2,x>−1, for the (standard) Gaussian cumulative distribution function, which is sharper than the classical inequality of Komatsu.     

-regularity of the Aronsson equation in

For a nonnegative, uniformly convex HC²(R²) with H(0)=0, if uC(Ω), ΩR², is a viscosity solution of the Aronsson equation (1.7), then uC¹(Ω). This generalizes the C¹-regularity theorem on infinity harmonic functions in R² by Savin [O. Savin, C¹-regularity for infinity harmonic functions in dimensions two, Arch. Ration. Mech. Anal. 176 (3) (2005) 351–361] to the Aronsson equation.     

Finite element analysis of an A– method for time-dependent Maxwell’s equations based on explicit-magnetic-field scheme

In this paper, error analysis of a finite element A– method for the time-dependent Maxwell’s equations is presented. An explicit-magnetic-field scheme is applied. Provided that the time-stepsize τ is sufficiently small, the proposed algorithm yields for finite time T an error of in the L²-norm for the electric field E and the magnetic field H, where h is the mesh size.     

Conditional random fields for entity extraction and ontological text coding

Previous research suggests that one field with a strong yet unsatisfied need for automatically extracting instances of various entity classes from texts is the analysis of socio-technical systems (Feldstein in Media in Transition MiT5, 2007; Hampe et al. in Netzwerkanalyse und Netzwerktheorie, 2007; Weil et al. in Proceedings of the 2006 Command and Control Research and Technology Symposium, 2006; Diesner and Carley in XXV Sunbelt Social Network Conference, 2005). Traditional as well as non-traditional and customized sets of entity classes and the relationships between them are often specified in ontologies or taxonomies. We present a Conditional Random Fields (CRF)-based approach to distilling a set of entities that are defined in an ontology originating from organization science. CRF, a supervised sequential machine learning technique, facilitates the derivation of relational data from corpora by locating and classifying instances of various entity classes. The classified entities can be used as nodes for the construction of socio-technical networks. We find the outcome sufficiently accurate (82.7 percent accuracy of locating and classifying entities) for future application in the described problem domain. We propose using the presented methodology as a crucial step in the process of advanced modeling and analysis of complex and dynamic networks.

A (2 + )-Approximation Scheme for Minimum Domination on Circle Graphs

The main result of this paper is a (2 + )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n²) time 8-approximation algorithm for this problem and then extend it to an time (2 + )-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + )-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs.     

On the continuation of solutions for elliptic equations in two variables

We consider nonlinear elliptic differential equations of second order in two variables

Full-size image

. Supposing analyticity of F, we prove analyticity of the real solution z=z(x,y) in the open set Ω. Furthermore, we show that z may be continued as a real analytic solution for F=0 across the real analytic boundary arc Γ∂Ω, if z satisfies one of the boundary conditions z= or z_n=ψ(x,y,z,z_t) on Γ with real analytic functions and ψ, respectively (z_n denotes the derivative of z w.r.t. the outer normal n on Γ and z_t its derivative w.r.t. the tangent). The proof is based on ideas of H. Lewy combined with a uniformization method. Studying quasilinear equations, we get somewhat better results concerning the initial regularity of the given solution and a little more insight.     

All-Pairs Small-Stretch Paths

Let G = (V, E) be a weighted undirected graph. A path between u, v  V is said to be of stretch t if its length is at most t times the distance between u and v in the graph. We consider the problem of finding small-stretch paths between all pairs of vertices in the graph G.It is easy to see that finding paths of stretch less than 2 between all pairs of vertices in an undirected graph with n vertices is at least as hard as the Boolean multiplication of two n × n matrices. We describe three algorithms for finding small-stretch paths between all pairs of vertices in a weighted graph with n vertices and m edges. The first algorithm, STRETCH₂, runs in Õ(n^3/2m^1/2) time and finds stretch 2 paths. The second algorithm, STRETCH_7/3, runs in Õ(n^7/3) time and finds stretch 7/3 paths. Finally, the third algorithm, STRETCH₃, runs in Õ(n²) and finds stretch 3 paths.Our algorithms are simpler, more efficient and more accurate than the previously best algorithms for finding small-stretch paths. Unlike all previous algorithms, our algorithms are not based on the construction of sparse spanners or sparse neighborhood covers.     

Tame roots of wild quivers

We study the tame behaviour of the representations of wild quivers Q via tame roots. A positive root d of Q is called a tame root if d is sincere and for any positive sub-root d^′ of d we have q(d^′)0, where q(d^′) is the Tits form of Q. We prove that a sincere root is a tame root if and only if for any decomposition of d into a sum of positive sub-roots d=d¹++d^s, there is at most one dⁱ with q(dⁱ)=0 and q(d^j)=1. This is the essential property of a tame root and it is an alternative way to define tame roots. Then we give the canonical decomposition of a tame root. At the end we prove our main result that for any wild graph, there are only finitely many tame roots.     

Typical primitive polynomials over integer residue rings

Let N be a product of distinct prime numbers and Z/(N) be the integer residue ring modulo N. In this paper, a primitive polynomial f(x) over Z/(N) such that f(x) divides x^s−c for some positive integer s and some primitive element c in Z/(N) is called a typical primitive polynomial. Recently typical primitive polynomials over Z/(N) were shown to be very useful, but the existence of typical primitive polynomials has not been fully studied. In this paper, for any integer m1, a necessary and sufficient condition for the existence of typical primitive polynomials of degree m over Z/(N) is proved.     

On multipartite posets

A poset P=(X,) is m-partite if X has a partition X=X₁X_m such that (1) each X_i forms an antichain in P, and (2) xy implies xX_i and yX_j where i<j. In this article we derive a tight asymptotic upper bound on the order dimension of m-partite posets in terms of m and their bipartite sub-posets in a constructive and elementary way.     

A homogeneous smoothing-type algorithm for symmetric cone linear programs

In this paper, we investigate a smoothing-type algorithm for solving the symmetric cone linear program （（SCLP） for short） by making use of an augmented system of its optimality conditions. The algorithm only needs to solve one system of linear equations and to perform one line search at each iteration. It is proved that the algorithm is globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, the algorithm may correctly detect solvability of （SCLP）. Furthermore, if （SCLP） has a solution, then the algorithm will generate a solution of （SCLP）, and if the problem is strongly infeasible, the algorithm will correctly detect infeasibility of （SCLP）.     

Operators Which Do Not Have the Single Valued Extension Property

In this paper we shall consider the relationships between a local version of the single valued extension property of a bounded operator T  L(X) on a Banach space X and some quantities associated with T which play an important role in Fredholm theory. In particular, we shall consider some conditions for which T does not have the single valued extension property at a point λ_o  C.     

Fast adaptive algorithms in the non-standard form for multidimensional problems

We present a fast, adaptive multiresolution algorithm for applying integral operators with a wide class of radially symmetric kernels in dimensions one, two and three. This algorithm is made efficient by the use of separated representations of the kernel. We discuss operators of the class (−Δ+μ²I)^−α, where μ0 and 0<α<3/2, and illustrate the algorithm for the Poisson and Schrödinger equations in dimension three. The same algorithm may be used for all operators with radially symmetric kernels approximated as a weighted sum of Gaussians, making it applicable across multiple fields by reusing a single implementation. This fast algorithm provides controllable accuracy at a reasonable cost, comparable to that of the Fast Multipole Method (FMM). It differs from the FMM by the type of approximation used to represent kernels and has the advantage of being easily extendable to higher dimensions.