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.     

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.     

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     

Specification and verification of database dynamics

Summary A framework is proposed for the structured specification and verification of database dynamics. In this framework, the conceptual model of a database is a many sorted first order linear tense theory whose proper axioms specify the update and the triggering behaviour of the database. The use of conceptual modelling approaches for structuring such a theory is analysed. Semantic primitives based on the notions of event and process are adopted for modelling the dynamic aspects. Events are used to model both atomic database operations and communication actions (input/output). Nonatomic operations to be performed on the database (transactions) are modelled by processes in terms of trigger/reaction patterns of behaviour. The correctness of the specification is verified by proving that the desired requirements on the evolution of the database are theorems of the conceptual model. Besides the traditional data integrity constraints, requirements of the form Under condition W, it is guaranteed that the database operation Z will be successfully performed are also considered. Such liveness requirements have been ignored in the database literature, although they are essential to a complete definition of the database dynamics.

Notation

Classical Logic Symbols (Appendix 1) for all (universal quantifier) - exists at least once (existential quantifier) - ¬ no (negation) - implies (implication) - is equivalent to (equivalence) - and (conjunction) - or (disjunction) Tense Logic Symbols (Appendix 1) G always in the future - G ₀ always in the future and now - F sometime in the future - F ₀ sometime in the future or now - H always in the past - H ₀ always in the past and now - P sometime in the past - P ₀ sometime in the past or now - X in the next moment - Y in the previous moment - L always - M sometime Event Specification Symbols (Sects. 3 and 4.1) (x) means immediately after the occurrence of x - (x) means immediately before the occurrence of x - (x) means x is enabled, i.e., x may occur next - { } ({w ₁} x{w ₂}) states that if w ₁ holds before the occurrence of x, then w ₂ will hold after the occurrence of x (change rule) - [ ] ([oa₁, ..., oa_n]x) states that only the object attributes oa₁, ..., oa _n are modifiable by x (scope rule) - {{ }} ({{w}}x) states that if x may occur next, then w holds (enabling rule) Process Specification Symbols (Sects. 5.3 and 5.4) :: for causal rules - for behavioural rules Transition-Pattern Composition Symbols (Sects. 5.2 and 5.3) ; sequential composition - ¦ choice composition - parallel composition - :| guarded alternative composition Location Predicates (Sect. 5.2) (z) means immediately after the occurrence of the last event of z (after) - (z) means immediately before the occurrence of the first event of z (before) - (z) means after the beginning of z and before the end of z (during) - ( z) means before the occurrence of an event of z (at)     

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.     

How can a complex square root be computed in an optimal way?

We give an optimality analysis for computations of complex square roots in real arithmetic by certain computation tress that use real square root operations. Improving standard elementary geometric constructions Schönhage suggests better methods which will be shown to be unimprobable. The iteration of such a procedure for 2 ^k -th roots is however improvable, and an improved version of it can also be shown to be unimprovable. In particular, repeated usage of an optimal square root procedure does not yield an optimal one for 2 ^k -th roots.To answer this kind of questions about resolution by real radicals we apply methods of real algebra which lead into the theory of real field, ring, and integral ring extensions.     

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.     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

Shallow circuits and concise formulae for multiple addition and multiplication

A theory is developed for the construction of carry-save networks with minimal delay, using a given collection of carry-save adders each of which may receive inputs and produce outputs using several different representation standards.The construction of some new carry-save adders is described. Using these carry-save adders optimally, as prescribed by the above theory, we get {, , }-circuits of depth 3.48 log₂ n and {, , }-circuits of depth 4.95 log₂ n for the carry-save addition ofn numbers of arbitrary length. As a consequence we get multiplication circuits of the same depth. These circuits put out two numbers whose sum is the result of the multiplication. If a single output number is required then the depth of the multiplication circuits increases respectively to 4.48 log₂ n and 5.95 log₂ n.We also get {, , }-formulae of sizeO (n ^3.13) and {, }-formulae of sizeO (n ^4.57) for all the output bits of a carry-save addition ofn numbers. As a consequence we get formulae of the same size for the majority function and many other symmetric Boolean functions.     

Interpretations of open default theories in non-monotonic logics

It is shown that the translation of an open default into a modal formula x(L(x)LM ₁ (x)...LM _m (x)w(x)) gives rise to an embedding of open default systems into non-monotonic logics.     

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.     

Design sensitivity analysis and optimization of nonlinear dynamic response for a motorcycle driving on a half-sine bump road

This paper analyses the design sensitivity of a suspension system with material and geometric nonlinearities for a motorcycle structure. The main procedures include nonlinear structural analysis, formulation of the problem with nonlinear dynamic response, design sensitivity analysis, and optimization. The incremental finite element method is used in structural analysis. The stiffness and damping parameters of the suspension system are considered as design variables. The maximum amplitude of nonlinear transient response at the seat is taken as the objective function during the optimization simulation. A more realistic finite element model for the motorcycle structure with elasto-damping elements of different material models is presented. A comparison is made of the optimum designs with and without geometric nonlinear response and is discussed.Nomenclature A amplitude of the excitation function - a ₀,a ₁ time integration constants for the Newmark method - ^t+t C _s secant viscous damping matrix at timet+t - ^t C _T tangent viscous damping matrix at timet - C linear part of ^t C _T - D _i ⁰ initial value of thei-th design variable - D _i instanenous value of thei-th design variables - ^t+t F^(t–1) total internal force vector at the end of iteration (i–1) and timet+t - ^t+t F _(NL) ^(i–1) nonlinear part of ^t+t F^(i–1) - f frequency of the excitation function - ^t+t K _s secant stiffness matrix at timet+t - ^t K _T tangent stiffness matrix at timet - K linear part of ^t K _T - effective stiffness matrix at timet - L distance between the wheel centres - M constant mass matrix - m _T number of solution time steps - NC number of constraint equations - Q nonlinear dynamic equilibrium equation of the structural system - ^t+t R external applied load vector at timet+t - t _e active time interval for the excitation function - ^t U displacement vector of the finite element assemblage at timet - velocity of the finite element assemblage at timet - ^t Ü acceleration vector of the finite element assemblage at timet - ^t+t U ⁽ⁱ⁾ displacement vector of the finite element assemblage at the end of iterationi and timet+t - velocity vector of the finite element assemblage at the end of iterationi and timet+t - ^t+t Ü⁽ⁱ⁾ acceleration vector of the finite element assemblage at the end of iterationi and timet+t - U ⁽ⁱ⁾ vector of displacement increments from the end of iteration (i–1) to the end of iterationi at timet+t - V driving speed of motorcycle - x vector of design variable - () quantities of variation - ₀ objective function - _i i-th constraint equation     

Sufficiency conditions for existence of an optimal feedback control in stochastic mechanics

In the framework of stochastic mechanics, the following problem is considered: in a set of admissible feedback controls v, with range inE ⁿ , find one minimizing the expectationE _sx { _s ^T L(t, (t), (t, (t)))dt + W _T ((T))} for all (s, x) [0,T) E ⁿ , whereL(t, x, ) = (/12)m ² – U(t, x) is the classical action integrand and is an-dimensional diffusion process in the weak sense, (see Bensoussan, 1982) with drift and diffusion coefficientD constant > 0.W _T andU are given real functions. Sufficiency conditions for the existence of such an optimal feedback control are given. Dedicated to George Leitmann Recommended by G.J. Olsder Presented at the Third Workshop on Control Mechanics in honor of George Leitmann, January 22–24, 1990, University of Southern California, Los Angeles, California (USA).     

Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

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.     

A Hyperbase for Binary Lattice Hyperidentities

We define an identity to be hypersatisfied by a variety V if, whenever the operation symbols of V, are replaced by arbitrary terms (of appropriate arity) in the operations of V, the resulting identity is satisfied by V in the usual sense. Whenever the identity is hypersatisfied by a variety V, we shall say that is a V hyperidentity. For example, the identity x + x y = x (x + y) is hypersatisfied by the variety L of all lattices. A proof of this consists of a case-by-case examination of { + , } {x, y, x y, x y}, the set of all binary lattice terms. In an earlier work, we exhibited a hyperbase ^L for the set of all binary lattice (or, equivalently, quasilattice) hyperidentities of type 2, 2. In this paper we provide a greatly refined hyperbase _L . The proof that _L is a hyperbase was obtained by using the automated reasoning program Otter 3.0.4.     

The dynamic clusters method in nonhierarchical clustering

Given a finite setE R ⁿ, the problem is to find clusters (or subsets of similar points inE) and at the same time to find the most typical elements of this set. An original mathematical formulation is given to the problem. The proposed algorithm operates on groups of points, called samplings (samplings may be called multiple centers or cores); these samplings adapt and evolve into interesting clusters. Compared with other clustering algorithms, this algorithm requires less machine time and storage. We provide some propositions about nonprobabilistic convergence and a sufficient condition which ensures the decrease of the criterion. Some computational experiments are presented.     

Simple adaptive stabilization of output feedback stabilizable distributed parameter systems

We show that the simple universal adaptive control lawu(t)=N(k(t))y(t)=|y(t)| ², withN(k)=(logk) cos((logk)) and 3+<1, stabilizes all detectable and stabilizable infinite dimensional systems of Pritchard-Salamon type which are externally stabilized by somescalar output feedback. The same controller is also shown to stabilize time varying systems satisfying the same type of output feedback stabilizability.     

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.     

Human intelligence and Turing Test

The Turing Test (TT) is criticised for various reasons, one being that it is limited to testing only human-like intelligence. We can read, for example, that TT is testing humanity, not intelligence, (Fostel, 1993), that TT is a test for human intelligence, not intelligence in general, (French, 1990), or that a perspective assumed by TT is parochial, arrogant and, generally, massively anthropocentric (Hayes and Ford, 1996). This limitation presumably causes a basic inadequacy of TT, namely that it misses a wide range of intelligence by focusing on one possibility only, namely on human intelligence. The spirit of TT enforces making explanations of possible machine intelligence in terms of what is known about intelligence in humans, thus possible specificity of the computer intelligence is ruled out from the oælset.This approach causes ire in some interpreters of the test and leads them to desire to create a theory of intelligence in general, thereby overcoming the limitations imposed by merely human intelligence. At times it is an emotion-laden discussion that does not hesitate to impute chauvinism in those limiting themselves to human-type intelligence.¹ This discussion is, by the way, not unlike the rhetoric used by some defenders of animal rights, who insist that an expression of superiority of men over animals is a token of speciesism, and speciesism is just a moral mistake of the same sort as racism and sexism.