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.     

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.     

Heaps and heapsort on secondary storage

A heap structure designed for secondary storage is suggested that tries to make the best use of the available buffer space in primary memory. The heap is a complete multi-way tree, with multi-page blocks of records as nodes, satisfying a generalized heap property. A special feature of the tree is that the nodes may be partially filled, as in B-trees. The structure is complemented with priority-queue operations insert and delete-max. When handling a sequence of S operations, the number of page transfers performed is shown to be O(∑_{i = 1}^S(1/P) log_(M/P)(N_i/P)), where P denotes the number of records fitting into a page, M the capacity of the buffer space in records, and N_i, the number of records in the heap prior to the ith operation (assuming P 1 and S> M c · P, where c is a small positive constant). The number of comparisons required when handling the sequence is O(∑_{i = 1}^S log₂ N_i). Using the suggested data structure we obtain an optimal external heapsort that performs O((N/P) log_(M/P)(N/P)) page transfers and O(N log₂ N) comparisons in the worst case when sorting N records.     

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.     

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.     

Biinfinite words with maximal recurrent unbordered factors

A finite non-empty word z is said to be a border of a finite non-empty word w if w=uz=zv for some non-empty words u and v. A finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. In this paper, we give two characterizations of the biinfinite words of the form ^ωuvu^ω, where u and v are finite words, in terms of its unbordered factors.

The main result of the paper states that the words of the form ^ωuvu^ω are precisely the biinfinite words w=a₋₂a₋₁a₀a₁a₂ for which there exists a pair (l₀,r₀) of integers with l₀<r₀ such that, for every integers ll₀ and rr₀, the factor a_la_l0a_r0a_r is a bordered word.

The words of the form ^ωuvu^ω are also characterized as being those biinfinite words w that admit a left recurrent unbordered factor (i.e., an unbordered factor of w that has an infinite number of occurrences “to the left” in w) of maximal length that is also a right recurrent unbordered factor of maximal length. This last result is a biinfinite analogue of a result known for infinite words.     

An element for static, vibration and buckling analysis of thick laminated plates

A conforming finite element formulation of the equations governing composite multilayered plates using Reddy's higher-order theory is presented. The element has eight degrees of freedom, u₀, v₀, w, ∂w/∂x, ∂w/∂y, ∂²w/∂x∂y, γ_x, γ_y, per node. The transverse displacement of the present element is described by a modified bicubic displacement function while the in-plane displacements and shear-rotations are interpolated quadraticly. The element is evaluated for its accuracy in the analysis of static, vibration, and buckling of anisotropic rectangular plates with different lamination schemes and boundary conditions. The conforming finite element described here for the higher-order theory gives fairly accurate results for displacements, stresses, buckling loads, and natural frequencies.     

Finding the minimum vertex distance between two disjoint convex polygons in linear time

Let V = v₁, v₂, …, v_m and W = w₁, w₂, …, w_n be two linearly separable convex polygons whose vertices are specified by their cartesian coordinates in order. An algorithm with O(m + n) worst-case time complexity is described for finding the minimum euclidean distance between a vertex v₁ in V and a vertex w_j in W. It is also shown that the algorithm is optimal.     

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.     

Behavior of the beta-splines with values of the parameters beta2 negative

In this paper we study the behavior of the beta-spline functions in the case the parameter β₂(i) is negative. We prove that a negative value exists so that if , the beta-spline functionsN_i(u) are positive. Moreover, if the control vertices are such that x₀ x_m−1, we have proved that the design curve keeps the properties already proved in the case β₂(i) 0.     

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.     

Analytic numerical solution of coupled semi-infinite diffusion problems

In this paper, we consider coupled semi-infinite diffusion problems of the form u_t(x, t)− A² u_xx(x,t) = 0, x> 0, t> 0, subject to u(0,t)=B and u(x,0)=0, where A is a matrix in , and u(x,t), and B are vectors in . Using the Fourier sine transform, an explicit exact solution of the problem is proposed. Given an admissible error and a domain D(x₀,t₀)={(x,t);0≤x≤x₀, t≥t₀ > 0, an analytic approximate solution is constructed so that the error with respect to the exact solution is uniformly upper bounded by in D(x₀, t₀).     

A multi-tree routing scheme using acyclic orientations

We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G=(V,E). The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication. A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N(v) of the destination v has at least k parent pointers. A capacity-k acorn A to destination v is k-vertex fault-tolerant to v. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w V−N(v) can be partitioned into k nonempty classes labeled 1,2,…,k such that any set of sink trees T₁,T₂,…,T_k are pairwise independent, where tree T_i is a sink tree generated by parent pointers labeled i together with the parent pointers into v. We present an linear time optimization algorithm for finding an acorn A of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity-k acorn A, yielding a k-independent sink tree generating scheme.     

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.     

Efficient algorithms for computing two nearest-neighbor problems on a rap

This paper makes an improvement of computing two nearest-neighbor problems of images on a reconfigurable array of processors (RAP) by increasing the bus width between processors. Based on a base-n system, a constant time algorithm is first presented for computing the maximum/minimum of N log N-bit unsigned integers on a RAP using N processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Then, two basic operations such as image component labeling and border following are also derived from it. Finally, these algorithms are used to design two constant time algorithms for the nearest neighbor black pixel and the nearest neighbor component problems on an N^1/2 × N^1/2 image using N^1/2 × N^1/2 processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Another contribution of this paper is that the execution time of the proposed algorithms is tunable by the bus width.     

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.     

Minimum cost source location problem with vertex-connectivity requirements in digraphs

Given a digraph (or an undirected graph) G=(V,E) with a set V of vertices v with nonnegative real costs w(v), and a set E of edges and a positive integer k, we deal with the problem of finding a minimum cost subset SV such that, for each vertex vV−S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in time in a digraph (or in time in an undirected graph), where n=|V| and m=|E|. Based on this, given a digraph and two integers k and ℓ, we also give a polynomial time algorithm for finding a minimum cost subset SV such that for each vertex vV−S, there are k vertex-disjoint paths from S to v as well as ℓ vertex-disjoint paths from v to S.     

On the sensitivity of camera calibration

The orientation position errors of an object's coordinate frame are determined when the offset of image centre and lens distortion are not included in the calibration process. The orientation and position errors are [(u₀)² + (v₀)²]^0.5/f and [(u²₀+v²₀)T²_z + (u²₀T²_z + v²₀T_y²)]^0.5/f, respectively, where f is the focal length, (u₀, v₀) is the offset of image centre and (T_x T_y T_z) is the position of an object. We also obtain the following conclusions: (a) The offset of image centre has little effect on the determinations of the position and orientation of a coordinate frame; (b) the lens distortion will not dramatically change the position and orientation of a coordinate frame; (c) the scale factor has a great effect on the position of a coordinate frame, and on the accuracy of measurement; (d) the offset of image centre is more sensitive than the lens distortion on the determinations of the position and orientation of a coordinate frame. Finally, some experimental results are given to demonstrate the theoretical analysis given in this paper.     

Entropy maximisation and open queueing networks with priorities and blocking

A review is carried out on the characterisation and algorithmic implementation of an extended product-form approximation, based on the principle of maximum entropy (ME), for a wide class of arbitrary finite capacity open queueing network models (QNMs) with service and space priorities. A single server finite capacity GE/GE/1/N queue with R (R>1) distinct priority classes, compound Poisson arrival processes (CPPs) with geometrically distributed batches and generalised exponential (GE) service times is analysed via entropy maximisation, subject to suitable GE-type queueing theoretic constraints, under preemptive resume (PR) and head-of-line (HOL) scheduling rules combined with complete buffer sharing (CBS) and partial buffer sharing (PBS) management schemes stipulating a sequence of buffer thresholds {N=(N₁,…,N_R),0<N_i≤N_i−1,i=2,…,R}. The GE/GE/1/N queue is utilised, in conjunction with GE-type first two moment flow approximation formulae, as a cost-effective building block towards the establishment of a generic ME queue-by-queue decomposition algorithm for arbitrary open QNMs with space and service priorities under repetitive service blocking with random destination (RS-RD). Typical numerical results are included to illustrate the credibility of the ME algorithm against simulation for various network topologies and define experimentally pessimistic GE-type performance bounds. Remarks on the extensions of the ME algorithm to other types of blocking mechanisms, such as repetitive service blocking with fixed destination (RS-FD) and blocking-after-service (BAS), are included.     

Confluent general-factorial difference and derivative operators and polynomial-exponential interpolation

A previous application of the Newton divided difference series of the displacement function E^z = (1 + Δ)^z = e ^Dz, where the operators Δ and D are the variables, to purely exponential interpolation employing general-factorial differences and derivatives, {Pi;^m_i=0 (Δ - S_i)}f(0) and {Pi;^m_i=0 (D - t_i)}f(0), in which the s_i's and t_i's are distinct[1], is here extended to mixed polynomial-exponential interpolation where the s_i's and t_i's are no longer distinct.