Nonlinear minimum-time control with pre- and post-actuation

This article studies the time-optimal output transition problem to change the system output, from an initial value (for all time ) to a final value (for all time ), for invertible nonlinear systems. The main contribution of the article is to show that the use of pre- and post-actuation input outside the transition interval I_T=[0,T] can reduce the transition time T beyond the standard bang–bang-type inputs for optimal state transition. The advantage of using pre- and post-actuation is demonstrated with an illustrative nonlinear example.     

Tracking control: Performance funnels and prescribed transient behaviour

Tracking of a reference signal (assumed bounded with essentially bounded derivative) is considered in the context of a class of nonlinear systems, with output y, described by functional differential equations (a generalization of the class of linear minimum-phase systems of relative degree one with positive high-frequency gain). The primary control objective is tracking with prescribed accuracy: given λ>0 (arbitrarily small), determine a feedback strategy which ensures that for every admissible system and reference signal, the tracking error e=y-r is ultimately smaller than λ (that is, e(t)<λ for all t sufficiently large). The second objective is guaranteed transient performance: the evolution of the tracking error should be contained in a prescribed performance funnel . Adopting the simple non-adaptive feedback control structure u(t)=-k(t)e(t), it is shown that the above objectives can be attained if the gain is generated by the nonlinear, memoryless feedback , where is any continuous function exhibiting two specific properties, the first of which ensures that if (t,e(t)) approaches the funnel boundary, then the gain attains values sufficiently large to preclude boundary contact, and the second of which obviates the need for large gain values away from the funnel boundary.     

Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions

A k-bounded pseudo-Boolean function is a real-valued function on n{0,1} that can be expressed as a sum of functions depending on at most k input bits. The k-bounded functions play an important role in a number of areas including molecular biology, biophysics, and evolutionary computation. We consider the problem of finding the Fourier coefficients of k-bounded functions, or equivalently, finding the coefficients of multilinear polynomials on n{−1,1} of degree k or less. Given a k-bounded function f with m non-zero Fourier coefficients for constant k, we present a randomized algorithm to find the Fourier coefficients of f with high probability in function evaluations. The best known upper bound was , where λ(n,m) is between and n depending on m. Our bound improves the previous bound by a factor of . It is almost tight with respect to the lower bound . In the process, we also consider the problem of finding k-bounded hypergraphs with a certain type of queries under an oracle with one-sided error. The problem is of self interest and we give an optimal algorithm for the problem.     

An iterative algorithm for solving a pair of matrix equations over generalized centro-symmetric matrices

A matrix is said to be a symmetric orthogonal matrix if . A matrix is said to be generalized centro-symmetric (generalized central anti-symmetric) with respect to P, if A=PAP (A=−PAP). The generalized centro-symmetric matrices have wide applications in information theory, linear estimate theory and numerical analysis. In this paper, we propose a new iterative algorithm to compute a generalized centro-symmetric solution of the linear matrix equations . We show, when the matrix equations are consistent over generalized centro-symmetric matrix Y, for any initial generalized centro-symmetric matrix Y₁, the sequence {Y_k} generated by the introduced algorithm converges to a generalized centro-symmetric solution of matrix equations . The least Frobenius norm generalized centro-symmetric solution can be derived when a special initial generalized centro-symmetric matrix is chosen. Furthermore, the optimal approximation generalized centro-symmetric solution to a given generalized centro-symmetric matrix can be derived. Several numerical examples are given to show the efficiency of the presented method.     

The global existence of nonlinear observers with linear error dynamics: A topological point of view

In this paper we show that under suitable assumptions, there exists a global homeomorphism Ψ(=Φ^-1) of which maps a nonlinear system onto a linear system with output injection . Thus, an observer for state x can be directly constructed as , which is a generalized version of Luenberger observer. An important feature of the obtained result is that there is no need to find the corresponding change of coordinates Ψ explicitly, which is different from current various existing approaches.     

The Kolmogorov Expression Complexity of Logics

The purpose of the paper is to propose a completely new notion of complexity of logics in finite-model theory. It is the Kolmogorov variant of the Vardi'sexpression complexity. We define it by considering the value of the Kolmogorov complexityC(L[]) of the infinite stringL[] of all truth values of sentences ofLin . The higher is this value, the more expressive is the logicLin . If is a class of finite models, then the value ofC(L[]) over all ∈ is a measure of expressive power ofLin . Unboundedness ofC(L[])−C(L′[]) for ∈ implies nonexistence of a recursive interpretation ofLinL′. A version of this statement with complexities modulo oracles implies the nonexistence of any interpretation ofLinL′. Thus the valuesC(L[]) modulo oracles constitute an invariant of the expressive power of logics over finite models, depending on their real (absolute) expressive power, and not on the syntax. We investigate our notion for fragments of the infinitary logic ^ω_∞ω: least fixed point logic (LFP) and partial fixed point logic (PFP). We prove a precise characterization of 0–1 laws for these logics in terms of a certain boundedness condition placed onC(L[]). We get an extension of the notion of a 0–1 law by imposing an upper bound on the value ofC(L[]) growing not too fast with cardinality of , which still implies inexpressibility results similar to those implied by 0–1 laws. We also discuss classes in whichC(PFP^k[]) is very high. It appears that then PFP or its simple extension can define all the PSPACE subsets of .     

Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem

We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties of small dimension. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve an elliptic curve discrete logarithm problem defined over in heuristic asymptotic running time ; and an elliptic problem over or a genus 2 problem over in heuristic asymptotic running time .     

Periodically switched stability induces exponential stability of discrete-time linear switched systems in the sense of Markovian probabilities

The conjecture that periodically switched stability implies absolute asymptotic stability of random infinite products of a finite set of square matrices, has recently been disproved under the guise of the finiteness conjecture. In this paper, we show that this conjecture holds in terms of Markovian probabilities. More specifically, let S_k∈C^n×n,1≤k≤K, be arbitrarily given K matrices and , where n,K≥2. Then we study the exponential stability of the following discrete-time switched dynamics S: where can be an arbitrary switching sequence.For a probability row-vector and an irreducible Markov transition matrix with , we denote by the Markovian probability on corresponding to . By using symbolic dynamics and ergodic-theoretic approaches, we show that, if S possesses the periodically switched stability then, (i) it is exponentially stable -almost surely; (ii) the set of stable switching sequences has the same Hausdorff dimension as . Thus, the periodically switched stability of a discrete-time linear switched dynamics implies that the system is exponentially stable for “almost” all switching sequences.     

Probabilistic integer sorting

We introduce a probabilistic sequential algorithm for stable sorting n uniformly distributed keys in an arbitrary range. The algorithm runs in linear time and sorts all but a very small fraction of the input sequences; the best previously known bound was . An EREW PRAM extension of this sequential algorithm sorts in O((n/p+lgp)lgn/lg(n/p+lgn)) time using p?n processors under the same probabilistic conditions. For a CRCW PRAM we improve upon the probabilistic bound of obtained by Rajasekaran and Sen to derive a bound. Additionally, we present experimental results for the sequential algorithm that establish the practicality of our method.     

Injectivity analysis using interval analysis: Application to structural identifiability

This paper presents a new numerical algorithm based on interval analysis able to prove that a differentiable function is injective. This algorithm also performs a partition of the domain A in subsets A_i where, for all , the cardinality of is constant. In the context of parameter estimation, we show how this algorithm provides an efficient and numerical method to study the structural identifiability of parametric models.     

Finding frequent items over sliding windows with constant update time

In this paper, we consider the problem of finding ?-approximate frequent items over a sliding window of size N. A recent work by Lee and Ting (2006) [7] solves the problem by giving an algorithm that supports query and update time, and uses space. Their query time and memory usage are essentially optimal, but the update time is not. We give a new algorithm that supports O(1) update time with high probability while maintaining the query time and memory usage as .     

Computing the nearest polynomial with a zero in a given domain by using piecewise rational functions

For a real univariate polynomial f and a closed complex domain D whose boundary C is a simple curve parameterized by a univariate piecewise rational function, a rigorous method is given for finding a real univariate polynomial such that has a zero in D and is minimal. First, it is proved that the minimum distance between f and polynomials having a zero at α∈C is a piecewise rational function of the real and imaginary parts of α. Thus, on C, the minimum distance is a piecewise rational function of a parameter obtained through the parameterization of C. Therefore, can be constructed by using the property that has a zero on C and computing the minimum distance on C. We analyze the asymptotic bit complexity of the method and show that it is of polynomial order in the size of the input.     

Multi-degree reduction of Bézier curves using reparameterization

L₂-norms are often used in the multi-degree reduction problem of Bézier curves or surfaces. Conventional methods on curve cases are to minimize , where and are the given curve and the approximation curve, respectively. A much better solution is to minimize , where is the closest point to point , that produces a similar effect as that of the Hausdorff distance. This paper uses a piecewise linear function L(t) instead of t to approximate the function φ(t) for a constrained multi-degree reduction of Bézier curves. Numerical examples show that this new reparameterization-based method has a much better approximation effect under Hausdorff distance than those of previous methods.     

Uniform metrical task systems with a limited number of states

We give a randomized algorithm (the “Wedge Algorithm”) of competitiveness for any metrical task system on a uniform space of k points, for any k?2, where , the kth harmonic number. This algorithm has better competitiveness than the Irani-Seiden algorithm if k is smaller than 10⁸. The algorithm is better by a factor of 2 if k<47.     

Resonance states of Ps using correlated wave functions

We have investigated the resonance states of positronium negative ion below the N=3, 4 and 5 Ps thresholds using highly correlated exponential wave functions. Resonance parameters (positions and widths) are extracted employing both the stabilization method and the complex-coordinate rotation method. In addition to many Feshbach resonances below the various Ps thresholds, we have identified two shape resonances with one each lying above the N=3 and N=5 thresholds, respectively. We have also identified three shape resonances with one lying above the N=3 threshold and two lying above N=4 threshold. The shape resonances associated with N=3 Ps threshold and some other Feshbach resonances are reported for the first time in the literature.     

Elementary approximation algorithms for prize collecting Steiner tree problems

This paper deals with approximation algorithms for the prize collecting generalized Steiner forest problem, defined as follows. The input is an undirected graph G=(V,E), a collection T={T₁,…,T_k}, each a subset of V of size at least 2, a weight function , and a penalty function . The goal is to find a forest F that minimizes the cost of the edges of F plus the penalties paid for subsets T_i whose vertices are not all connected by F. Our main result is a -approximation for the prize collecting generalized Steiner forest problem, where n2 is the number of vertices in the graph. This obviously implies the same approximation for the special case called the prize collecting Steiner forest problem (all subsets T_i are of size 2). The approximation algorithm is obtained by applying the local ratio method, and is much simpler than the best known combinatorial algorithm for this problem.Our approach gives a -approximation for the prize collecting Steiner tree problem (all subsets T_i are of size 2 and there is some root vertex r that belongs to all of them). This latter algorithm is in fact the local ratio version of the primal-dual algorithm of Goemans and Williamson [M.X. Goemans, D.P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal on Computing 24 (2) (April 1995) 296–317]. Another special case of our main algorithm is Bar-Yehuda's local ratio -approximation for the generalized Steiner forest problem (all the penalties are infinity) [R. Bar-Yehuda, One for the price of two: a unified approach for approximating covering problems, Algorithmica 27 (2) (June 2000) 131–144]. Thus, an important contribution of this paper is in providing a natural generalization of the framework presented by Goemans and Williamson, and later by Bar-Yehuda.