Convergence of MUSCL Relaxing Schemes to the Relaxed Schemes for Conservation Laws with Stiff Source Terms

We consider the convergence and stability property of MUSCL relaxing schemes applied to conservation laws with stiff source terms. The maximum principle for the numerical schemes will be established. It will be also shown that the MUSCL relaxing schemes are uniformly l ¹- and TV-stable in the sense that they are bounded by a constant independent of the relaxation parameter , the Lipschitz constant of the stiff source term and the time step t. The Lipschitz constant of the l ¹ continuity in time for the MUSCL relaxing schemes is shown to be independent of and t. The convergence of the relaxing schemes to the corresponding MUSCL relaxed schemes is then established.     

On the valuedness of finite transducers

Summary We investigate the valuedness of finite transducers in connection with their inner structure. We show: The valuedness of a finite-valued nondeterministic generalized sequential machine (NGSM) M with n states and output alphabet is at most the maximum of (1-1/#) · (2 ^k ₁ · k ₃ ) ⁿ · n ⁿ ·# ^{n 3 ·k} ₄ / ³ and 1/#·(2 ^k ₂ ·k ₃ ·(1+k ₄ )) ⁿ ·n ⁿ where k ₁6.25 and k ₂11.89 are constants and k ₃1 and k ₄0 are local structural parameters of M. There are two simple criteria which characterize the infinite valuedness of an NGSM. By these criteria, it is decidable in polynomial time whether or not an NGSM is infinite-valued. In both cases, # > 1 and # = 1, the above upper bound for the valuedness is almost optimal. By reduction, all results can be easily generalized to normalized finite transducers.     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

A Delay-Averaged Logistic Model

For the equation x(t) = x(t) (1-(1/) _t-- ^t- x(u)du), > 0, > 0, > 0, conditions for the stability of a nonzero stationary solution under small perturbations are determined.     

On structured perturbations for two classes of linear infinite-dimensional systems

This paper considers two classes of infinite-dimensional systems described by an abstract differential equationx (t) = (A + BC)x(t),x(0) =x ₀, on a Hilbert space, whereA, B, C are linear, possibly unbounded operators and is an unknown, linear, bounded perturbation. The two classes of systems are defined in terms of properties imposed on the triple (A, B, C). It is proved that for every the perturbed system (A + EF, B, C) inherits all the properties of the unperturbed system {A, B, C}) if (A, E, F) and {A, B, F} are in the same class.     

Optimum design of circular tubes loaded in compression in preand post-buckling ranges

Based on Kuhn-Tucker optimality criteria, using a grapho-analytical method, simple closed formulae are given for optimal diameter and thickness of centrally compressed struts of circular hollow section. These dimensions minimize the cross-sectional area and fulfill the design constraints. In the prebuckling range overall and local elastic buckling constraints are defined. In the post-buckling range the optimal sizes can be calculated using the formulae valid for the prebuckling range, but instead of the limitingD/t-ratio, valid for semi-compact tubes, the plastic limitingD/t-ratio should be used to avoid local buckling. The comparative calculations show the mass savings achievable by using a higher-strength steel as well as the larger axial shortening of struts made of higher-strength steel.Notation A cross-sectional area - (6) - D diameter - E modulus of elasticity - f overall buckling factor, (3), Fig. 2 - I moment of inertia - k end restraint factor, (4) - L strut length - P factored axial compressive force - P _cr critical buckling force, (3) - P _y squash load, (3) - r radius of gyration - t thickness - factor, (17) - = D/t diameter/thickness ratio - _L.el limiting elasticD/t-ratio - _L.pl limiting plasticD/t-ratio - = D/L diameter/length ratio - =kL/r slenderness - =/ _E modified slenderness - Euler slenderness - _y yield stress - axial shortening - _y =P _y L/(AE) _pl see (17)     

A note on dense and nondense families of complexity classes

In a model for a measure of computational complexity, , for a partial recursive functiont, letR _t denote all partial recursive functions having the same domain ast and computable within timet. Let = {R _t |t is recursive} and let = { |_i is actually the running time function of a computation}. and are partially ordered under set-theoretic inclusion. These partial orderings have been extensively investigated by Borodin, Constable and Hopcroft in [3]. In this paper we present a simple uniform proof of some of their results. For example, we give a procedure for easily calculating a model of computational complexity for which is not dense while is dense. In our opinion, our technique is so transparent that it indicates that certain questions of density are not intrinsically interesting for general abstract measures of computational complexity, . (This is not to say that similar questions are necessarily uninteresting for specific models.)Supported by NSF Research Grants GP6120 and GJ27127.     

Query answering via cooperative data inference

This paper proposes the use of accessible information (data/knowledge) to infer inaccessible data in a distributed database system. Inference rules are extracted from databases by means of knowledge discovery techniques. These rules can derive inaccessible data due to a site failure or network partition in a distributed system. Such query answering requires combining incomplete and partial information from multiple sources. The derived answer may be exact or approximate. Our inference process involves two phases to reason with reconstructed information. One phase involves using local rules to infer inaccessible data. A second phase involves merging information from different sites. We shall call such reasoning processes cooperative data inference. Since the derived answer may be incomplete, new algebraic tools are developed for supporting operations on incomplete information. A weak criterion called toleration is introduced for evaluating the inferred results. The conditions that assure the correctness of combining partial results, known as sound inference paths, are developed. A solution is presented for terminating an iterative reasoning process on derived data from multiple knowledge sources. The proposed approach has been implemented on a cooperative distributed database testbed, CoBase, at UCLA. The experimental results validate the feasibility of this proposed concept and can significantly improve the availability of distributed knowledge base/database systems.List of notation Mapping - --< Logical implication - = Symbolic equality - ==< Inference path - Satisfaction - Toleration - Undefined (does not exist) - Variable-null (may or may not exist) - ^* Subtuple relationship - ^* s-membership - s-containment - Open subtuple - Open s-membership - Open s-containment - _P Open base - P Program - I Interpretation - DIP Data inference program - t Tuples - R Relations - Ø Empty interpretation - Open s-union - Open s-interpretation - Set of mapping from the set of objects to the set of closed objects - W Set of attributes - _W Set of sound inference paths on the set of attributes W - Set of relational schemas in a DB that satisfy MVD - ⁺ Range closure of W wrt      

Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity

We investigate three-dimensional visibility problems for scenes that consist ofn non-intersecting spheres. The viewing point moves on a flightpath that is part of a circle at infinity given by a planeP and a range of angles {(t)¦t[01]} [02]. At timet, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angle(t) (orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time0(n + k + p) logn), wheren is the number of spheres in the scene;p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.The second author was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem () = min{c ^t x¦Ax =b + ¯b,x 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function (). As a consequence, the optimality intervals form a partition of the closed interval {; ¦()¦ < }. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of () is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.This research was partially funded by the United States Navy-Office of Naval Research under Contract N00014-87-K-0202. Its financial support is gratefully acknowledged.     

Relativized polynomial hierarchies extending two levels

The existence of relativized polynomial hierarchies extending exactly two levels is shown. More precisely, oraclesX andY are constructed such thatNP(X) ₂ ^{P, X} = ₂ ^{P, X} and ₂ ^{P, Y} ₂ ^{P, Y} = ₂ ^{P, Y} . These results answer a question posed by Baker, Gill, and Solovay ([1]) and generalize their constructions of relativized polynomial hierarchies extending 0 resp. 1 level; i.e.,P(A) = NP(A) resp.P(B) NP(B) = coNP(B) for recursive oraclesA andB.     

Context-free text grammars

A text is a triple=(, ₁, ₂) such that is a labeling function, and ₁ and ₂ are linear orders on the domain of ; hence may be seen as a word (, ₁) together with an additional linear order ₂ on the domain of . The order ₂ is used to give to the word (, ₁) itsindividual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introducecontext-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of ashapely context-free text grammar also investigated in this paper.     

Conditions for the Light-Traffic Insensitivity to Loss Probability in a GI/G/m/0 Queueing System

A loss queueing system GI/G/m/0 is considered. Let a(x) be a p.d.f. of interarrival intervals. Assume that this function behaves like cx^-1 for small x. Further let B(x) be a d.f. of service time; (1/) be the mean service time. Conditions are derived for the light-traffic insensitivity of the loss probability to the form of B(x) as (/ ) 0. In particular, the condition = 1 is necessary. Estimates for the loss probability are obtained.     

Shape optimization of elasto-plastic bodies under plane strains: Sensitivity analysis and numerical implementation

Optimal shape design problems for an elastic body made from physically nonlinear material are presented. Sensitivity analysis is done by differentiating the discrete equations of equilibrium. Numerical examples are included.Notation U ^ad set of admissible continuous design parameters - U _h ^ad set of admissible discrete design parameters - function fromU _h ^ad defining shape of body - _h function fromU _h ^ad defining approximated shape of body - vector of nodal values of _h - { _n} sequence of functions tending to - () domain defined by - K bulk modulus - shear modulus - penalty parameter for contact condition - V() space of virtual displacements in() - V _h(_h) finite element approximation ofV() - J cost functional - J _h discretized cost functional - J algebraic form ofJ _h - (u) stress tensor - e(u) strain tensor - K stiffness matrix - f force vector - b(q) term arising from nonlinear boundary conditions - q vector of nodal degrees of freedom - p vector of adjoint state variables - J Jacobian of isoparametric mapping - |J| determinant ofJ - N vector of shape function values on parent element - L matrix of shape function derivatives on parent element - G matrix of Cartesian derivatives of shape functions - X matrix of nodal coordinates of element - D matrix of elastic coefficients - B strain-displacement matrix - _P part of boundary where tractions are prescribed - _u part of boundary where displacements are prescribed - variable part of boundary - strain invariant     

Optimal design of rigid-plastic annular plates with piecewise constant thickness

Rigid-plastic stepped annular plates under uniform pressure load are considered. Both plate edges are supported. Four types of boundary conditions are studied. Tresca's yield condition is used. Such plate dimensions are sought for which the plate of constant volume has the maximal load carrying capacity.Notation a, d, R, h ₁, h₂ plate dimensions (Fig. 1) - Q ^* shear force - Q dimensionless shear force - M _r ^* radial bending moment - M ₁ dimensionless radial bending moment - M _t ^* circumferential bending moment - M ₂ dimensionless circumferential bending moment - M _k maximum value of bending moments in the rigid region - p ^* uniform pressure load - p dimensionless uniform pressure load - r radial coordinate - x dimensionless radial coordinate - , , dimensionless parameters for plate (5) - V plate volume - dimensionless plate volume - M ₀ ^* yield moment - ₀ yield stress - p ₀ load carrying capacity - p ₀ ^m maximum value of the load carrying capacity - p ₀ ^u load carrying capacity for uniform plate - ^m, ^m optimal parameters, which correspond to the maximum value ofp ₀ - s _i radius of circle between different plastic stages - () /x     

Symbolic computation of robot models for geometric parameters identification with singularity analysis

The computation of the geometrical parameters identification model of a robot arm leads to an intrinsic extended Jacobian matrix. This matrix is often singular and its manual computation is tedious and may lead to error. A computer assisted procedure is developed to compute this matrix symbolically and to check its singularity. The program GPIM is developed in Pascal and works on PC's for this purpose. Jacobian singularity is checked using its symbolic expressions with the aid of a proposed table for robot arm parameters to obtain a minimum set of identified parameters. This program can be used for simple chain robot arms having revolute (R) and/or prismatic (P) joints including the case of consecutive near parallel axes. TH8 robot arm of type RPPRRR having two pairs of consecutive near parallel axes is studied to show the program efficiency and how singularity is eliminated.Nomenclature a _i Denavit-Hartenberg parameter. - C _i ,C _i andC ₁₂ cos _i , cos _i and cos ( ₁ + ₂). - J ₀, J Basic Jacobian and Jacobian matrices. - J _a , J _r , J , J and J Sub-Jacobian matrices. - J _0a , J _0r , J ₀, J ₀ and J ₀ Intrinsic sub-Jacobian matrices. - m Work space dimensions. - n Number of moving links of the robot arm. - p Number of pairs of consecutive near parallel axes. - P _i,i+1 and P _li [3×1] position vectors. - Q _pi , Q _ai , Q _ri , Q _i , Q _i and Q _i [4×4] differential operator matrices. - r _i Denavit-Hartenberg parameter. - R _l , R _i , R _i+1 and R _n+1 Base, links i–1, i and n coordinate frames. - R _i,i+1 and R _1i [3×3] orientation matrices. - S _i , S _i and S ₁₂ sin _i , sin _i and sin ₁ + ₂. - T _i,i+1 and T _1i [4×4] homogeneous transformation matrices. - X [m×1] robot arm operational coordinates. - 1st columns of the orientation matrices, and associated tensors. - 2nd columns of the orientation matrices, and associated tensors. - 3rd columns of the orientation matrices, and associated tensors. - _i Denavit-Hartenberg parameter. - _i Twist angle parameter. - X Changes in robot arm operational coordinates. - , ls and rr Changes in robot arm geometrical parameters, and their least square and ridge regression estimated changes. - _i Denavit-Hartenberg parameter. - , ^c and ⁿ Robot geometrical parameters and their correct and nominal values. - pi, ai, ri, i, i and i [4×4] differential operator matrices. - and ^–1 [3×3] conversion matrix and its inverse.     

Efficient Solution of Multi-Term Fractional Differential Equations Using P(EC)<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>E Methods

We investigate strategies for the numerical solution of the initial value problem with initial conditions where 0<₁<₂<<. Here y ⁽ _j ) denotes the derivative of order _j >0 (not necessarily _j ) in the sense of Caputo. The methods are based on numerical integration techniques applied to an equivalent nonlinear and weakly singular Volterra integral equation. The classical approach leads to an algorithm with very high arithmetic complexity. Therefore we derive an alternative that leads to lower complexity without sacrificing too much precision. Mathematics Subject Classification: Primary 65L05; Secondary 65L06, 65L20     

Transient performance of flow over a rotating object placed eccentrically inside a microchannel—numerical study

Industrial applications today are demanding the implementation of microelectromechanical systems (MEMS) into their products. These are mechanical devices that are able to perform work, and yet have characteristic lengths less than 1 mm. As a result, the Reynolds number is typically low, which indicates the dominance of viscous forces. When a cylinder is placed eccentrically inside a microchannel, where the rotor axis is perpendicular to the channel axis, a net force is transferred to the fluid as a result of the unequal shear stresses on the upper and lower surfaces of the rotor. Consequently, this causes the surrounding fluid in the channel to displace towards the microchannel outlet. The present numerical investigation is a comparative study of transient flow behavior in a microchannel with rotating cylinders with different cross-sectional geometries. The effects of channel height, eccentricity, Reynolds number, and pump load were studied, as well as the development of their respective streamlines and pressure contours. The steady state results were compared with existing numerical and experimental results, and the comparisons showed very good agreement.List of symbols C_D cylinder drag coefficient - C_L cylinder lift coefficient - C_M cylinder moment coefficient - d diagonal length of rotor (m) - F_L lift force on cylinder per unit length (N/m) - F_D drag force on cylinder per unit length (N/m) - h channel height (m) - L perimeter of rotor (m) - M moment on cylinder (N m) - ṁ mass flow rate (kg/s) - P_in inlet pressure (Pa) - P_out outlet pressure (Pa) - P* non-dimensional pressure - P channel pressure rise (Pa) - P* non-dimensional pressure rise - Q non-dimensional volume flow rate - Re Reynolds number - R normal distribution ratio - S curve length (m) - S non-dimensional channel height - t time (s) - t* non-dimensional time - t time step size (s) - ū average velocity inside microchannel (m/s) - u* non-dimensional average velocity - U cylinder surface velocity (m/s) - fluid velocity vector (m/s) - y_c distance from channel axis to cylinder center (m)Greek letters body forces per unit mass (m/s²) - rotor eccentricity - fluid dynamic viscosity (Pa s) - fluid kinematic viscosity (m²/s) - angle sweep over surface, =s/L (rad) - fluid density (kg/m³) - fluid shear stress (Pa) - * non-dimensional fluid shear stress - rotor angular velocity     

A combinatorial property of EOL languages

Let be an alphabet and II its nontrivial binary partition. Each word over can uniquely be decomposed in subwords (called blocks) consisting of letters of II _i only,i {1,2}. LetK ^*.K has a long block property (with respect to II), abbreviated asLB-property, if there exists a functionf:N ⁺ N ⁺ such that for everyw K and every positive integerm the number of blocks of length at mostm inw is bounded byf(m). K has a clustered block property (with respect to II), abbreviated asCB-property, if there exists a positive integern _o and a growing functiong:N ⁺ N ⁺ such that for everyw K and for every positive integerm the blocks of length at mostm can be covered by at mostn _o segments of length at mostg(m).It is proved that aCB-property always implies aLB-property but not necessarily other way around. It is proved that an EOL language has aLB-property if and only if it has aCB-property.     

On a random Volterra integral equation

Summary Tsokos [12] showed the existence of a unique random solution of the random Volterra integral equation (*)x(t; ) = h(t; ) + _o ^t k(t, ; )f(, x(; )) d, where , the supporting set of a probability measure space (,A, P). It was required thatf must satisfy a Lipschitz condition in a certain subset of a Banach space. By using an extension of Banach's contraction-mapping principle, it is shown here that a unique random solution of (*) exists whenf is (, )-uniformly locally Lipschitz in the same subset of the Banach space considered in [12].