Moments of conjugacy classes of binary words

For each nonempty binary word w=c₁c₂c_q, where c_i{0,1}, the nonnegative integer ∑_i=1^q (q+1−i)c_i is called the moment of w and is denoted by M(w). Let [w] denote the conjugacy class of w. Define M([w])={M(u): u[w]}, N(w)={M(u)−M(w): u[w]} and δ(w)=max{M(u)−M(v): u,v[w]}. Using these objects, we obtain equivalent conditions for a binary word to be an -word (respectively, a power of an -word). For instance, we prove that the following statements are equivalent for any binary word w with |w|2: (a) w is an -word, (b) δ(w)=|w|−1, (c) w is a cyclic balanced primitive word, (d) M([w]) is a set of |w| consecutive positive integers, (e) N(w) is a set of |w| consecutive integers and 0N(w), (f) w is primitive and [w]St.     

Fast evaluation of radial basis functions: I

This paper describes some new techniques for the rapid evaluation and fitting of radial basic functions. The techniques are based on the hierarchical and multipole expansions recently introduced by several authors for the calculation of many-body potentials. Consider in particular the N term thin-plate spline, s(x) = Σ_j=1^N d_jφ(x−x_j), where φ(u) = |u|²log|u|, in 2-dimensions. The direct evaluation of s at a single extra point requires an extra O(N) operations. This paper shows that, with judicious use of series expansions, the incremental cost of evaluating s(x) to within precision ε, can be cut to O(1+|log ε|) operations. In particular, if A is the interpolation matrix, a_i,j = φ(x_i−x_j, the technique allows computation of the matrix-vector product Ad in O(N), rather than the previously required O(N²) operations, and using only O(N) storage. Fast, storage-efficient, computation of this matrix-vector product makes pre-conditioned conjugate-gradient methods very attractive as solvers of the interpolation equations, Ad = y, when N is large.     

1-Inverses for polynomial matrices of non-constant rank

Let p₁, … p_t be polynomials in ⁿ with a variety V of common zeros contained in a suitable open set U. Explicit formulas are provided to construct rational functions λ₁, … λ_s such that Σ_i=1^sp_iλ_i 1, and such that the singularities of the λ_i are contained in U. This result is applied to compute rational functions-valued 1-inverses of matrices with polynomial coefficients, which do not have constant rank, while retaining control over the location of the singularities of the rational functions themselves.     

New spectral lower bounds on the bisection width of graphs

The communication overhead is a major bottleneck for the execution of a process graph on a parallel computer system. In the case of two processors, the minimization of the communication can be modeled using the graph bisection problem. The spectral lower bound of λ₂|V|/4 for the bisection width of a graph is widely known. The bisection width is equal to λ₂|V|/4 iff all vertices are incident to λ₂/2 cut edges in every optimal bisection.

We present a new method of obtaining tighter lower bounds on the bisection width. This method makes use of the level structure defined by the bisection. We define some global expansion properties and we show that the spectral lower bound increases with this global expansion. Under certain conditions we obtain a lower bound depending on λ₂^β|V| with . We also present examples of graphs for which our new bounds are tight up to a constant factor. As a by-product, we derive new lower bounds for the bisection widths of 3- and 4-regular Ramanujan graphs.     

A simple solution to the l optimization problem

It is pointed out in this brief paper that the l¹ optimization problem min_{Q ε lqp¹} | H − U * Q * V |₁, H ε l_mn¹, U ε l_mq¹, V ε l_pn¹ can be solved in one step rather than two. The solution of the dual problem is obviated by the direct solution of the primal problem via linear programming. The method here is applicable to finite-dimensional problems or approximating finite-dimensional problems, in the general case.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

Analytic-numerical solutions with a priori error bounds for time-dependent mixed partial differential problems

The aim of this paper is double. First, we point out that the hypothesis D(t₁)D(t₂) = D(t₂)D(t₁) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω(t₀,t₁) = [0,p] × [t₀,t₁], for mixed problems of the type u_t(x,t) − D(t)u_xx(x,t) = 0, 0 < x < p, t> 0, subject to u(0,t) = u(p,t) = 0 and u(x,0) = F(x) is proposed. Here, u(x,t) and F(x) are r-component vectors, D(t) is a C^{r × r} valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) (D(t) + D(t)^H) is bigger than δ. An illustrative example is included.     

On canonical number systems

Let be such that d1,p_d=1,p₀2 and . We are proving in this note a new criterion for the pair to be a canonical number system. This enables us to prove that if p₂,…,p_d−1,∑_i=1^dp_i0 and p₀>2∑_i=1^d|p_i|, then is a canonical number system.     

Geometric design of motions constrained by a contacting surface pair

We discuss the following problem which arises in robot motion planning, NC machining and computer animation: Given are a fixed surface Ψ and N positions Φ_i of a moving surface Φ such that the Φ_i are in point contact with Ψ. Compute a smooth and fair Euclidean gliding motion Φ(t) of the surface Φ on the surface Ψ which interpolates (or approximates) the given positions Φ_i at time instances t_i. First we generalize interpolatory variational subdivision algorithms for curves to curves on surfaces. Second we study an unconstraint motion design algorithm which we then extend to the main contribution of this paper, an algorithm for the design of a motion constraint by a contacting surface pair. Both motion design algorithms use a feature point representation of the moving surface, subdivision algorithms for curves, instantaneous kinematics, and ideas from line geometry. Geometric methods are used for the numerical solution of the arising optimization problems.     

Uniform and optimal schemes for stiff initial-value problems

We formulate a class of difference schemes for stiff initial-value problems, with a small parameter ε multiplying the first derivative. We derive necessary conditions for uniform convergence with respect to the small parameter ε, that is the solution of the difference scheme u_i^h satisfies |u_i^h−u(x_i)| Ch, where C is independent of h and ε. We also derive sufficient conditions for uniform convergence and show that a subclass of schemes is also optimal in the sense that |u_i^h−u(x_i)| C min (h, ε). Finally, we show that this class contains higher-order schemes.     

Nonexistence of finite-dimensional filters for conditional statistics of the cubic sensor problem

Consider the cubic sensor dx = dw, dy = x³dt + dv where w, v are two independent Brownian motions. Given a function φ(x) of the state x let φ_t(x) denote the conditional expectation given the observations y_s, 0 s t. This paper consists of a rather detailed discussion and outline of proof of the theorem that for nonconstant φ there cannot exist a recursive finite-dimensional filter for φ driven by the observations.     

Comparing parallel Newton''s method with parallel Laguerre''s method

Newton's and Laguerre's methods can be used to concurrently refine all separated zeros of a polynomial P(z). This paper analyses the rate convergence of both procedures, and its implication on the attainable number n of correct figures. In two special cases the number m of iterations required to reach an accuracy η = 10⁻ⁿ is shown to grow as log_λ n, where λ = 3 for Newton's and λ = 4 for Laguerre's. In the general case m is shown to grow linearly with n for both procedures. An assessment of the efficiency of the two methods is also given, by evaluating the computational complexity of operations in circular arithmetic, and the efficiency indices of the two iterative schemes.     

Two ant-colony algorithms for minimizing total flowtime in permutation flowshops

The problem of scheduling in flowshops with the objective of minimizing total flowtime is studied. For solving the problem two ant-colony algorithms are proposed and analyzed. The first algorithm refers to some extent to ideas by Stuetzle [Stuetzle, T. (1998). An ant approach for the flow shop problem. In: Proceedings of the sixth European Congress on intelligent techniques and soft computing (EUFIT '98) (Vol. 3) (pp. 1560–1564). Aachen: Verlag Mainz] and Merkle and Middendorf [Merkle, D., & Middendorf, M. (2000). An ant algorithm with a new pheromone evaluation rule for total tardiness problems. In: Proceedings of the EvoWorkshops 2000, lecture notes in computer science 1803 (pp. 287–296). Berlin: Springer]. The second algorithm is newly developed. The proposed ant-colony algorithms have been applied to 90 benchmark problems taken from Taillard [Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278–285]. A comparison of the solutions yielded by the ant-colony algorithms with the best heuristic solutions known for the benchmark problems up to now, as published in extensive studies by Liu and Reeves [Liu, J., & Reeves, C.R. (2001). Constructive and composite heuristic solutions to the P//ΣC_i scheduling problem. European Journal of Operational Research, 132, 439–452, and Rajendran and Ziegler [Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155, 426–438], shows that the presented ant-colony algorithms are better, on an average, than the heuristics analyzed by Liu and Reeves and Rajendran and Ziegler.     

Paired-domination in inflated graphs

The inflation G_I of a graph G with n(G) vertices and m(G) edges is obtained from G by replacing every vertex of degree d of G by a clique K_d. A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired domination number γ_p(G) is the minimum cardinality of a paired dominating set of G. In this paper, we show that if a graph G has a minimum degree δ(G)2, then n(G)γ_p(G_I)4m(G)/[δ(G)+1], and the equality γ_p(G_I) = n(G) holds if and only if G has a perfect matching. In addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree.     

Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

Asymptotic expansions of Hankel transforms of functions with logarithmic singularities

Asymptotic expansions as λ → +∞ are obtained for the Hankel transform

whereJ_v(t) is the Bessel function of the first kind and v is a fixed complex number. The function \tf(t) is allowed to have an asymptotic expansion near the origin of the form

Here, Re _n ↑ +∞ and β_n is an arbitrary complex number.     

Infinite words and biprefix codes

Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set {v_ii0} of (finite) words on A such that ƒ=v₀v₁…v_i…, {v_ii1} is a biprefix code and v_i≠v_j for positive integers i≠j.     

Computational complexity of distributed detection problems with information constraints

For a system consisting of a set of sensors S = {S₁, S₂, …, S_m} and a set of objects O = {O₁, O₂, …, O_n}, there are information constraints given by a relation R S × O such that (S_i, O_j) R if and only if S_i is capable of detecting O_j. Each (S_i, O_j) R is assigned a confidence factor (a positive real number) which is either explicitly given or can be efficiently computed. Given that a subset of sensors have detected obstacles, the detection problem is to identify a subset H O with the maximum confidence value. The computational complexity of the detection problem, which depends on the nature of the confidence factor and the information constraints, is the main focus of this paper. This problem exhibits a myriad of complexity levels ranging from a worst-case exponential (in n) lower bound in a general case to an O(m + n) time solvability. We show that the following simple versions of a detection problem are computationally intractable: (a) deterministic formulation, where confidence factors are either 0 or 1; (b) uniform formulation where (S_i, O_j) R, for all S_i S, O_j O; (c) decomposable systems under multiplication operation. We then show that the following versions are solvable in polynomial (in n) time: (a) single object detection; (b) probabilistically independent detection; (c) decomposable systems under additive and nonfractional multiplicative measures; and (d) matroid systems.     

Properties of Noncentral Dirichlet Distributions

Let X₁,…, X_r+1 be independent random variables, X_iGa (a_i, θ, δ_i), i = 1,…, r + 1. Define and V_i = X_i/X_r+1, i = 1,…, r. Then, (U₁,…, U_r) and (V₁,…, V_r) follow noncentral Dirichlet Type 1 and Type 2 distributions, respectively. In this article several properties of these distributions and their connections with the uniform, the noncentral multivariate-F and the noncentral multivariate-t distributions are discussed.