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.     

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.     

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.     

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.     

Generalization of rectangular element stiffness matrix and thermal load vector associated with a0 + a1x + a2y + a3xy type interpolation rule

Explicit expressions for the element stiffness matrix K and element load vector p for the rectangular plane-stress and plane-strain finite elements associated with Ψ(x, y) = a₀ + a₁x + a₂y + a₃xy type interpolation rule are given for the general anisotropic material in xy-planc subjected to non-uniform temperature increases. The expressions are optimized with respect to the numerical operations required for the computation of K and p, and they are valid for special cases of material properties and thermal loading.     

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₀).     

Bivariate hermite subdivision

A subdivision scheme for constructing smooth surfaces interpolating scattered data in R³ is proposed. It is also possible to impose derivative constraints in these points. In the case of functional data, i.e., data are given in a properly triangulated set of points {(x_i, y_i)}_i=1^N from which none of the pairs (x_i,y_i) and (x_j,y_j) with i≠j coincide, it is proved that the resulting surface (function) is C¹. The method is based on the construction of a sequence of continuous splines of degree 3. Another subdivision method, based on constructing a sequence of splines of degree 5 which are once differentiable, yields a function which is C² if the data are not ‘too irregular’. Finally the approximation properties of the methods are investigated.     

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.     

Order-configuration functions: Mathematical characterizations and applications to digital signal and image processing

We call a function f in n variables an order-configuration function if for any x₁,…, x_n such that x_i1 … x_in we have f(x₁,…, x_n) = x_t, where t is determined by the n-tuple (i₁,…, i_n) corresponding to that ordering. Equivalently, it is a function built as a minimum of maxima, or a maximum of minima. Well-known examples are the minimum, the maximum, the median, and more generally rank functions, or the composition of rank functions. Such types of functions are often used in nonlinear processing of digital signals or images (for example in the median or separable median filter, min-max filters, rank filters, etc.). In this paper we study the mathematical properties of order-configuration functions and of a wider class of functions that we call order-subconfiguration functions. We give several characterization theorems for them. We show through various examples how our concepts can be used in the design of digital signal filters or image transformations based on order-configuration functions.     

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.     

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.     

A refined analysis of laminated plates by finite element displacement methods—I. Fundamentals and static analysis

This and a companion paper (Computers and Structures 26, 915–923, 1987) present a local finite element model based on a refined approximate theory for thick anisotropic laminated plates. The three-dimensional problem is reduced to a two-dimensional case by assuming piecewise linear variation of the in-plane displacements u and ρ and a constant value of the lateral displacement w across the thickness. By using a substructuring technique the present model is demonstrated to be practical and economical. The static bending stresses, transverse shearing stresses and in-plane displacements are predicted in the present paper. The vibration and buckling analyses will be presented in the second paper. Comparison with both exact three-dimensional analysis and a high-order plate bending theory shows that this model provides results which are accurate and acceptable for all ranges of thickness and modular ratio.     

Bending analysis of rectangular moderately thick plates using spline finite element method

A bending analysis of rectangular, moderately thick plates with general boundary conditions is presented using the spline element method. The cubic B spline interpolate functions are used to construct the field function of generalized displacements w, φ_itxand φ_ity. The spline finite element equations are derived based on the potential energy principle. For simplicity, the boundary conditions, which consist of three local spline points, are amended to fit specified boundary conditions. The shear effect is considered in the formulations. A number of numerical examples are described for rectangular, moderately thick plates. Since the cubic B spline interpolate functions have sufficient continuity and are piecewise polynomial, so the present numerical solutions show not only that the method gives accurate results, but also that the unified solutions of thick and thin plates can be directly obtained; the trouble with the so-called shear locking phenomenon does not occur here.     

Algorithms of discretization of algebraic spatial curves on homogeneous cubical grids

In this paper new methods of discretization (integer approximation) of algebraic spatial curves in the form of intersecting surfaces P(x, y, z) = 0 and Q(x, y, z) = 0 are analyzed.

The use of homogeneous cubical grids G(h³) to discretize a curve is the essence of the method. Two new algorithms of discretization (on 6-connected grid G_6c(h³) and 26-connected grid G₂₆(h³)) are presented based on the method above. Implementation of the algorithms for algebraic spatial curves is suggested. The elaborated algorithms are adjusted for application in computer graphics and numerical control of machine tools.     

Timoshenko beam finite element with four dof and convergence of O(h)

In situations where transverse shear deformations and rotary inertia in beams are important, elements based on the Timoshenko beam theory are useful. Among the two-noded, four DOF elements derived from the minimum total potential energy principle, the HTK. element proposed by Hughes et al. using linear displacement functions for both w and θ and the T1CC4 element proposed by Tessler et al. using quadratic displacement function for w and linear displacement function for θ are well known in the literature. The convergence of the HTK element in the thin beam situation has been too poor due to shear locking but by using selective integration this element can be shown to be equivalent to the T1CC4 element which has a rate of convergence of O(h²). In this paper a five DOF element with w and θ at the end nodes and θ at the middle node and based on the cubic displacement function for w and the quadratic displacement function for θ is first developed. Statically condensing the middle rotational DOF, the well-known (4 × 4) stiffness matrix using the φ-factor defined as φ = 12EI/kGAL² and hitherto obtained only through a flexibility approach or closed-form solution of the governing equations of the Timoshenko beam theory is derived. This element based on cubic displacement function for w has rate of convergence of O(h⁴), is completely free of shear locking and performs equally well in thin as well as thick beam situations.     

A small gain theorem for linear stochastic systems

A well-known result in linear control theory is the so-called “small gain” theorem stating that if given two plants with transfer matrix functions T₁ and T₂ in H^∞ such that T₁ < γ and T₂ < 1/γ, when coupling T₂ to T₁ such that u₂ = y₁ and u₁ = y₂ one obtains an internally stable closed system. The aim of the present paper is to describe a corresponding result for stochastic systems with state-dependent white noise.     

Numerical inverse isoparametric mapping in remeshing and nodal quantity contouring

In finite element analysis, isoparametric mapping defined as [(ξ, η) → (x, y): X = N_iξ_i] is widely used. It is a one-to-one mapping and its construction is especially elegant for elements of a variable number of nodes showing its versatile applicability to model curved boundaries. In certain analyses, such as remeshing in dynamic analyses or contouring and others, the inverse of this mapping is inevitably valuable, but its determination is not so straightforward. To avoid solving a system of nonlinear equations, generally an iterative technique of order N² in a two-dimensional mesh is often resorted to. In the paper, this technique is improved by systematically bisecting along a predefined line that reduces the iterations to only order N. Its applications in remeshing and nodal quantity contouring are demonstrated and a possible extension for stress contouring is also discussed. The FORTRAN subroutines for the technique proposed are also given.     

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.     

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.