On closure properties of GapP

We study the closure properties of the function classes GapP and GapP₊. We characterize the property of GapP₊ being closed under decrement and of GapP being closed under maximum, minimum, median, or division by seemingly implausible collapses among complexity classes, thereby giving evidence that these function classes don't have the stated closure properties.We show a similar result concerning operations we callbit cancellation andbit insertion: Given a functionf GapP and a polynomialtime computable function , we ask whether the functionsf ^* (x) andf ⁺ (x) are in GapP or not, wheref ^* (x) is obtained fromf(x) by cancelling the (x)-th bit in the binary representation off(x), andf ⁺ (x) is obtained fromf(x) by inserting a bit at position (x) in the binary representation off(x). We give necessary and sufficient conditions for GapP being closed under bit cancellation and bit insertion, respectively.     

Controllability of general nonlinear systems

Consider the nonlinear system $$\dot x(t) = f(x(t)) + \sum\limits_{i = 1}^m {u_i (t)g_i (x(t)), x(0) = x_0 \in M}$$ whereM is aC ^∞ realn-dimensional manifold,f, g ₁,?.,g _m areC ^∞ vector fields onM, andu ₁ ,..,u _m are real-valued controls. Ifm=n?1 andf, g ₁ ,?,g _m are linearly independent, then the system is called a hypersurface system, and necessary and sufficient conditions for controllability are known. For a generalm, 1 ≤m ≤n?1, and arbitraryC ^∞ vector fields,f, g ₁ ,?,g _m , assume that the Lie algebra generated byf, g ₁ ,?,g _m and by taking successive Lie brackets of these vector fields is a vector bundle with constant fiber (vector space) dimensionp onM. By Chow's Theorem there exists a maximalC ^∞ realp-dimensional submanifoldS ofM containingx ₀ with the generated bundle as its tangent bundle. It is known that the reachable set fromx ₀ must contain an open set inS. The largest open subsetU ofS which is reachable fromx ₀ is called the region of reachability fromx ₀. IfO is an open subset ofS which is reachable fromx ₀,S we find necessary conditions and sufficient conditions on the boundary ofO inS so thatO = U. Best results are obtained when it is assumed that the Lie algebra generated byg ₁,?,g _m and their Lie brackets is a vector bundle onM.     

Feedback transformations on tori

Here we investigate the problem of transforming a nonlinear system on the torusT ⁿ by using global feedback and global changes of coordinates into an invariant system (i.e., a control system of whichf andg _i are (left and right) invariant vector fields whenT ² is considered as a Lie group). We provide a complete answer whenn=2 and give a sufficient condition and necessary conditions in the more general case.     

Boundary control of weakly nonlinear wave equations with an application to galloping of transmission lines

Exponential decay is proven for a class of initial boundary value problems for the equationw _tt-c ₀ ² w_xx=f(w_t). The boundary condition isc ₀w_x+rw_t=0 atx=1 andw(0,t)=0. Iff satisfies a global Lipschitz condition, no restrictions are placed on the initial conditions, but if this is relaxed to a local Lipschitz condition, the initial data are assumed to be sufficiently small. These theorems are motivated in part by an application to modeling of galloping transmission lines. A theorem about boundedness of solutions without boundary damping is proven also. A global Lipschitz condition is assumed here, but the theorem is believed to be more generally true.     

Theory and performance of a subroutine for solving Volterra Integral Equations

The author considers Volterra Integral Equations of either of the two forms $$u(x) = f(x) + \int\limits_a^x {k(x - t)g(u(t))dt, a \leqslant } x \leqslant b,$$ wheref, k, andg are continuous andg satisfies a local Lipschitz condition, or $$u(x) = f(x) + \int\limits_a^x {\sum\limits_{j = 1}^m {c_j (x)g_j (t,u(t))dt} ,} $$ wheref,c _j , andg _j ,j=1,2,...,m, are continuous and eachg _j satisfies a local Lipschitz condition in its second variable. It is shown that in each case the respective integral equation can be solved by conversion to a system of ordinary differential equations which can be solved by referring to a described FORTRAN subroutine. Subroutine VE1. In the case of the convolution equation, it is shown how VE1 converts the equation via a Chebyshev expansion, and a theorem is proved, and implemented in VE1, wherein the solution error due to truncation of the expansion can be simultaneously computed at the discretion of the user. Some performance data are supplied and a comparison with other standard schemes is made. Detailed performance data and a program listing are available from the author.     

Global optimization methods for engineering applications: A review

A review of the methods for global optimization reveals that most methods have been developed for unconstrained problems. They need to be extended to general constrained problems because most of the engineering applications have constraints. Some of the methods can be easily extended while others need further work. It is also possible to transform a constrained problem to an unconstrained one by using penalty or augmented Lagrangian methods and solve the problem that way. Some of the global optimization methods find all the local minimum points while others find only a few of them. In any case, all the methods require a very large number of calculations. Therefore, the computational effort to obtain a global solution is generally substantial. The methods for global optimization can be divided into two broad categories: deterministic and stochastic. Some deterministic methods are based on certain assumptions on the cost function that are not easy to check. These methods are not very useful since they are not applicable to general problems. Other deterministic methods are based on certain heuristics which may not lead to the true global solution. Several stochastic methods have been developed as some variation of the pure random search. Some methods are useful for only discrete optimization problems while others can be used for both discrete and continuous problems. Main characteristics of each method are identified and discussed. The selection of a method for a particular application depends on several attributes, such as types of design variables, whether or not all local minima are desired, and availability of gradients of all the functions.Notation Number of equality constraints - () ^T A transpose of a vector - A A hypercubic cell in clustering methods - Distance between two adjacent mesh points - Probability that a uniform sample of sizeN contains at least one point in a subsetA ofS - A(v, x) Aspiration level function - A The set of points with cost function values less thanf(x _G ^* ) +. Same asA _f () - A _f () A set of points at which the cost function value is within off(x _G ^* ) - A () A set of points x with[f(x)] smaller than - A _N The set ofN random points - A _q The set of sample points with the cost function value f _q - _Q The contraction coefficient; –1 _Q 0 - _R The expansion coefficient; _E > 1 - _R The reflection coefficient; 0 < _R 1 - A _x () A set of points that are within the distance from x _G ^* - D Diagonal form of the Hessian matrix - det() Determinant of a matrix - d _j A monotonic function of the number of failed local minimizations - d _t Infinitesimal change in time - d _x Infinitesimal change in design - A small positive constant - (t) A real function called the noise coefficient - ₀ Initial value for(t) - exp() The exponential function - f ^(c) The record; smallest cost function value over X^(C) - [f(x)] Functional for calculating the volume fraction of a subset - Second-order approximation tof(x) - f(x) The cost function - An estimate of the upper bound of global minimum - f ^E The cost function value at x^E - f ^L The cost function value at x^L - f _opt The current best minimum function value - f ^P The cost function value at x ^P - f ^Q The cost function value at x ^Q - f _q A function value used to reduce the random sample - f ^R The cost function value at x ^R - f ^S The cost function value at x^S - f _{T F min} A common minimum cost function value for several trajectories - f _{TF opt} The best current minimum value found so far forf _{TF min} - f ^W The cost function value at x ^W - G Minimum number of points in a cell (A) to be considered full - The gamma function - A factor used to scale the global optimum cost in the zooming method - Minimum distance assumed to exist between two local minimum points - gi(x) Constraints of the optimization problem - H The size of the tabu list - H(x^*) The Hessian matrix of the cost function at x^* - h _j Half side length of a hypercube - h _m Minimum half side lengths of hypercubes in one row - I The unity matrix - ILIM A limit on the number of trials before the temperature is reduced - J The set of active constraints - K Estimate of total number of local minima - k Iteration counter - The number of times a clustering algorithm is executed - L Lipschitz constant, defined in Section 2 - L The number of local searches performed - _i The corresponding pole strengths - log () The natural logarithm - LS Local search procedure - M Number of local minimum points found inL searches - m Total number of constraints - m(t) Mass of a particle as a function of time - m() TheLebesgue measure of thea set - Average cost value for a number of random sample of points inS - N The number of sample points taken from a uniform random distribution - n Number of design variables - n(t) Nonconservative resistance forces - n _c Number of cells;S is divided inton _c cells - NT Number of trajectories - Pi (3.1415926) - P _i ^(j) Hypersphere approximating thej-th cluster at stagei - p(x ⁽ⁱ⁾⁾ Boltzmann-Gibbs distribution; the probability of finding the system in a particular configuration - pg A parameter corresponding to each reduced sample point, defined in (36) - Q An orthogonal matrix used to diagonalize the Hessian matrix - _i (i = 1, K) The relative size of thei-th region of attraction - r _i ^(j) Radius of thej-th hypersp here at stagei - R _x ^* Region of attraction of a local minimum x^* - r _j Radius of a hypersphere - r A critical distance; determines whether a point is linked to a cluster - R ⁿ A set ofn tuples of real numbers - A hyper rectangle set used to approximateS - S The constraint set - A user supplied parameter used to determiner - s The number of failed local minimizations - T The tabu list - t Time - T(x) The tunneling function - T _c (x) The constrained tunneling function - T _i The temperature of a system at a configurationi - TLIMIT A lower limit for the temperature - TR A factor between 0 and 1 used to reduce the temperature - u(x) A unimodal function - V(x) The set of all feasible moves at the current design - v(x) An oscillating small perturbation. - V(y⁽ⁱ⁾) Voronoi cell of the code point y⁽ⁱ⁾ - v^–1 An inverse move - v _k A move; the change from previous to current designs - w(t) Ann-dimensional standard. Wiener process - x Design variable vector of dimensionn - x^# A movable pole used in the tunneling method - x⁽⁰⁾ A starting point for a local search procedure - X^(c) A sequence of feasible points {x⁽¹⁾, x⁽²⁾,,x^(c)} - x(t) Design vector as a function of time - X^* The set of all local minimum points - x^* A local minimum point forf(x) - x^*(i) Poles used in the tunneling method - x _G ^* A global minimum point forf(x) - Transformed design space - The velocity vector of the particle as a function of time - Acceleration vector of the particle as a function of time - x ^C Centroid of the simplex excluding x ^L - x ^c A pole point used in the tunneling method - x ^E An expansion point of x ^R along the direction x ^C x ^R - x ^L The best point of a simplex - x ^P A new trial point - x ^Q A contraction point - x ^R A reflection point; reflection of x ^W on x ^C - x ^S The second worst point of a simplex - x ^W The worst point of a simplex - The reduced sample point with the smallest function value of a full cell - Y The set of code points - y ⁽ⁱ⁾ A code point; a point that represents all the points of thei-th cell - z A random number uniformly distributed in (0,1) - Z ^(c) The set of points x where [f ^(c) – ] is smaller thanf(x) - []₊ Max (0,) - | | Absolute value - The Euclidean norm - f[x(t)] The gradient of the cost function     

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)     

The existence of solutions,stability, and linearization of volterra systems

LetB be a Banach space ofR _n valued continuous functions on [0, ) withfB. Consider the nonlinear Volterra integral equation (^*)x(t)+ _o ^t K(t,s,x(s))ds. We use the implicit function theorem to give sufficient conditions onB andK (t,s,x) for the existence of a unique solutionxB to (^*) for eachf B with f ^B sufficiently small. Moreover, there is a constantM>0 independent off with Mf^B.Part of this work was done while the author was visiting at Wright State University.     

Uniqueness for ordinary differential equations

Various criteria are known for assuring uniqueness of the solution of a system ofn ordinary differential equations,x = f(t, x), with initial conditionx(t ₀) = x₀. Most of these involve some sort of relaxed Lipschitz condition onf(t, x), with respect tox, valid on an open setD R ¹⁺ⁿ which contains the point (t ₀, x₀). The present paper generalizes (and unifies) a number of known uniqueness criteria to cover cases when (t ₀, x₀) lies on the boundary ofD. Research partially supported by NSF Grant GP-37838.     

Systems of Strings with High Mutual Complexity

Consider a binary string x ₀ of Kolmogorov complexity K(x ₀) n. The question is whether there exist two strings x ₁ and x ₂ such that the approximate equalities K(x _i x _j ) n and K(x _i x _j , x _k ) n hold for all 0 i, j, k 2, i j k, i k. We prove that the answer is positive if we require the equalities to hold up to an additive term O(log K(x ₀)). It becomes negative in the case of better accuracy, namely, O(log n).     

Numerical optimization of a new robotized glass blowing process

To answer an increasing need for glass product manufacturing in both small and medium series, the first glass-blower robot was recently developed. In the face of this new technology, which particularly interests crystal glass-makers, expertise remains the main decision-making element which intervenes in the choices of the design and implementation of these new processes. Finite element models of this new blowing process were developed. After the analysis of the process and of these stages, an initial sensibility study allowed us to find the essential parameters for the success of the operation. With the results of these sensitivity analyses, an optimizer was developed to adjust virtually the forming process of a linear cylindrical vase by determining the optimal forming parameters. A second optimization allowed us to determine the initial shape of the parison, an essential parameter in the successful forming of a convex cylindrical vase. Finally, the numerical tools were validated during trial campaigns carried out in crystal glass-makers.Symbols A ^s _i normalized functions n ^s _i - C ₁ constraint equation - E ( p _i ) error function - ep _s ^* vase thickness obtained by finite element models - prescribed designers vase thickness - glass distribution calculated in a point m after disturbing - glass distribution obtained in a point m - G first derivative of the penalization function _j ( p) - H second derivative of the penalization function _j ( p) - I identity matrix - J Jacobian matrix of the error function E ( p _i ) - M number of comparison points - m point of the vase - N ^s number of parameters - n ^s _i standardized functions of N ^s variations - P _{s 1} pressure of free blowing - p ^s _i ith parameter p ^s - T _init initial temperature after reheating - t _{f 2} time of vertical creep - t _m time of first shaping - t _{s 1} time of free blowing - ₁ angle of tilted creep - Levenberg–Marquardt parameter - ₁ positive scalar - _j ( p) penalization function     

Geometric properties of linearizable control systems

In this paper the distributions associated with a non-linear system of the form $$\frac{{dx}}{{dt}} = f(x) + \sum\limits_{\alpha = 1}^m {u_\alpha (t)g_\alpha (x)} ,f(0) = 0andx \in U_0 \subset R^n$$ are studied in relation to nonlinear state feedback $$u(x,v) = \hat a(x) + \hat S(x)v$$ withâ, u, v ∈ R ^m and ? a nonsingularm×m matrix withâ, ? functions ofx. Bothf andg are vector fields onU ₀, generally assumed to be real analytic. Two nested families of distributions {G ^j } and {M ^j } associated with the system are examined with emphasis on generic points ofU ₀, where it is shown that the usual conditions for feedback linearizability contain some redundancy. A characterization of state linearizability in terms of invariant factors of the equivalent linear form are given, and a criterion in terms of the distributions for a type of partial linearization is found.     

Counting connected components of a semialgebraic set in subexponential time

Let a semialgebraic set be given by a quantifier-free formula of the first-order theory of real closed fields withk atomic subformulae of the typef _i0 for 1ik, where the polynomialsf _i[X ₁,...,X _n] have degrees deg(f _i)<d and the absolute value of each (integer) coefficient off _i is at most 2M. An algorithm is exhibited which counts the number of connected components of the semialgebraic set in time (M (kd)^{n 20})^{O (1)}. Moreover, the algorithm allows us to determine whether any pair of points from the set are situated in the same connected component.     

A Representation of the Interval Hull of a Tolerance Polyhedron Describing Inclusions of Function Values and Slopes

Given a nonempty set of functions

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

Rate of convergence of nonlinear integral operators for functions of bounded variation

The aim of this paper is to study the behavior of the operators T _λ defined by

Compact Numerical Quadrature Formulas for Hypersingular Integrals and Integral Equations

In the first part of this work, we derive compact numerical quadrature formulas for finite-range integrals $I[f]=\int^{b}_{a}f(x)\,dx$ , where f(x)=g(x)|x?t| ^?? , ?? being real. Depending on the value of ??, these integrals are defined either in the regular sense or in the sense of Hadamard finite part. Assuming that g??C ^??[a,b], or g??C ^??(a,b) but can have arbitrary algebraic singularities at x=a and/or x=b, and letting h=(b?a)/n, n an integer, we derive asymptotic expansions for ${T}^{*}_{n}[f]=h\sum_{1\leq j\leq n-1,\ x_{j}\neq t}f(x_{j})$ , where x _j =a+jh and t??{x ₁,??,x _n?1}. These asymptotic expansions are based on some recent generalizations of the Euler?CMaclaurin expansion due to the author (A.?Sidi, Euler?CMaclaurin expansions for integrals with arbitrary algebraic endpoint singularities, in Math. Comput., 2012), and are used to construct our quadrature formulas, whose accuracies are then increased at will by applying to them the Richardson extrapolation process. We pay particular attention to the case in which ??=?2 and f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ , which arises in the context of periodic hypersingular integral equations. For this case, we propose the remarkably simple and compact quadrature formula $\widehat{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)-\pi^{2} g(t)h^{-1}$ , and show that $\widehat{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, and that it is exact for a class of singular integrals involving trigonometric polynomials of degree at most n. We show how $\widehat{Q}_{n}[f]$ can be used for solving hypersingular integral equations in an efficient manner. In the second part of this work, we derive the Euler?CMaclaurin expansion for integrals $I[f]=\int^{b}_{a} f(x)dx$ , where f(x)=g(x)(x?t) ^?? , with g(x) as before and ??=?1,?3,?5,??, from which suitable quadrature formulas can be obtained. We revisit the case of ??=?1, for which the known quadrature formula $\widetilde{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)$ satisfies $\widetilde{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, when f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ . We show that this formula too is exact for a class of singular integrals involving trigonometric polynomials of degree at most n?1. We provide numerical examples involving periodic integrands that confirm the theoretical results.     

Self-organizing neural networks for the analysis and representation of data: Some financial cases

Many recent papers have dealt with the application of feedforward neural networks in financial data processing. This powerful neural model can implement very complex nonlinear mappings, but when outputs are not available or clustering of patterns is required, the use of unsupervised models such as self-organizing maps is more suitable. The present work shows the capabilities of self-organizing feature maps for the analysis and representation of financial data and for aid in financial decision-making. For this purpose, we analyse the Spanish banking crisis of 1977–1985 and the Spanish economic situation in 1990 and 1991, making use of this unsupervised model. Emphasis is placed on the analysis of the synaptic weights, fundamental for delimiting regions on the map, such as bankrupt or solvent regions, where similar companies are clustered. The time evolution of the companies and other important conclusions can be drawn from the resulting maps.Characters and symbols used and their meaning nx x dimension of the neuron grid, in number of neurons - ny y dimension of the neuron grid, in number of neurons - n dimension of the input vector, number of input variables - (i, j) indices of a neuron on the map - k index of the input variables - w _ijk synaptic weight that connects thek input with the (i, j) neuron on the map - W _ij weight vector of the (i, j) neuron - x _k input vector - X input vector - (t) learning rate - _o starting learning rate - _f final learning rate - R(t) neighbourhood radius - R₀ starting neighbourhood radius - R _f final neighbourhood radius - t iteration counter - t _rf number of iterations until reachingR _f - t _f number of iterations until reaching _f - h(·) lateral interaction function - standard deviation - for every - d (x, y) distance between the vectors x and y     

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.     

PI k mass production and an optimal circuit for the Nečiporuk slice

Letf: {0,1} ⁿ {0,1} ^m be anm-output Boolean function inn variables.f is called ak-slice iff(x) equals the all-zero vector for allx with Hamming weight less thank andf(x) equals the all-one vector for allx with Hamming weight more thank. Wegener showed that PI _k -set circuits (set circuits over prime implicants of lengthk) are at the heart of any optimum Boolean circuit for ak-slicef. We prove that, in PI _k -set circuits, savings are possible for the mass production of anyFX, i.e., any collectionF ofm output-sets given any collectionX ofn input-sets, if their PI _k -set complexity satisfiesSC _m (FX)3n+2m. This PI _k mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n+o(n) for the Neiporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity (n ^3/2). Finally, the new circuit for the Neiporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.