Finite gain stabilization requires analog control

A causal feedback map, taking sequences of measurements and producing sequences of controls, is denoted as finite set if, within any finite time horizon, its range is in a finite set. Bit-rate constrained or digital control are particular cases of finite-set feedback. In this paper, we show that the finite gain (FG) l_p stabilization, with 1p∞, of a discrete-time, linear and time-invariant unstable plant is impossible by finite-set feedback. In addition, we show that, under finite-set feedback, weaker (local) versions of FG l_p stability are also impossible. These facts are not obvious, since recent results have shown that input to state stabilization is viable by bit-rate constrained control. In view of such existing work, this paper leads to two conclusions: (1) even when input to state stability is attainable by finite-set feedback, small changes in the amplitude of the external excitation may cause, in relative terms, a large increase in the amplitude of the state (2) FG l_p stabilization requires logarithmic precision around zero. Since our conclusions hold with no assumption on the feedback structure, they cannot be derived from existing results. We adopt an information theoretic viewpoint, which also brings new insights into the problem of stabilization.     

On the stability of a weighted diamond of real polynomials

Recently, a subset of the robust stability literature concentrated on the so-called diamond of polynomials. In this paper, we study the weighted diamond Q_w defined as

, where the center q^*, the weights w₀, w₁, 3dot , w_n > 0 and the radius r > 0 are given. For this family, we show that an extreme point result holds if and only if a certain ‘interlacing condition’ on the weights is satisfied.     

A Kharitonov‐like theorem for robust stability independent of delay of interval quasipolynomials

In this paper, a Kharitonov‐like theorem is proved for testing robust stability independent of delay of interval quasipolynomials, p(s)+∑eq_k(s), where p and q_k's are interval polynomials with uncertain coefficients. It is shown that the robust stability test of the quasipolynomial basically reduces to the stability test of a set of Kharitonov‐like vertex quasipolynomials, where stability is interpreted as stability independent of delay. As discovered in (IEEE Trans. Autom. Control 2008; 53 :1219–1234), the well‐known vertex‐type robust stability result reported in (IMA J. Math. Contr. Info. 1988; 5 :117–123) (See also (IEEE Trans. Circ. Syst. 1990; 37 (7):969–972; Proc. 34th IEEE Conf. Decision Contr., New Orleans, LA, December 1995; 392–394) does contain a flaw. An alternative approach is proposed in (IEEE Trans. Autom. Control 2008; 53 :1219–1234), and both frequency sweeping and vertex type robust stability tests are developed for quasipolynomials with polytopic coefficient uncertainties. Under a specific assumption, it is shown in (IEEE Trans. Autom. Control 2008; 53 :1219–1234) that robust stability independent of delay of an interval quasipolynomial can be reduced to stability independent of delay of a set of Kharitonov‐like vertex quasipolynomials. In this paper, we show that the assumption made in (IEEE Trans. Autom. Control 2008; 53 :1219–1234) is redundant, and the Kharitonov‐like result reported in (IEEE Trans. Autom. Control 2008; 53 :1219–1234) is true without any additional assumption, and can be applied to all quasipolynomials. The key idea used in (IEEE Trans. Autom. Control 2008; 53 :1219–1234) was the equivalence of Hurwitz stability and ?_‐o‐stability for interval polynomials with constant term never equal to zero. This simple observation implies that the well‐known Kharitonov theorem for Hurwitz stability can be applied for ?_‐o‐stability, provided that the constant term of the interval polynomial never vanishes. However, this line of approach is based on a specific assumption, which we call the CNF‐assumption. In this paper, we follow a different approach: First, robust ?_‐o‐stability problem is studied in a more general framework, including the cases where degree drop is allowed, and the constant term as well as other higher‐orders terms can vanish. Then, generalized Kharitonov‐like theorems are proved for ?_‐o‐stability, and inspired by the techniques used in (IEEE Trans. Autom. Control 2008; 53 :1219–1234), it is shown that robust stability independent of delay of an interval quasipolynomial can be reduced to stability independent of delay of a set of Kharitonov‐like vertex quasipolynomials, even if the assumption adopted in (IEEE Trans. Autom. Control 2008; 53 :1219–1234) is not satisfied. Copyright © 2009 John Wiley & Sons, Ltd.     

Dynamics of the difference equation

We study the invariant interval, the character of semicycles, the global stability, and the boundedness of the difference equation

where the initial conditions x_−k,…,x₋₁,x₀ are nonnegative, and p,q>0.     

On the characterization of linear and linearizable automata by a superposition principle

This paper deals with the superponability of linear and linearizable automata. Automata linear in GF(p),p2, with input and output sets {0, 1,,p-1} and with arbitrary initial state are characterized as the class of automata superponable, i.e. permutable, with respect to a functionax+(1-a)x. The casep=2 requires special considerations. The inputoutput behaviour of this automata can be described by generalized impulse responses. Using instead of GF(p) an arbitrary commutative field on the same basic set {0,1,,p-1} some of the functions nonlinear in GF(p) are linear in this field. These functions are called linearizable. Linearizable functions are characterized by a functional equation and solvability conditions and as polynomials in GF(p). Thus the well known theory of linear automata can be extended to linearizable automata.     

Stabilization of some fractional delay systems of neutral type

In this note, we give new stability tests which enable one to fully characterize the H_∞-stability of systems with transfer function , where h>0 and p,q,r are real polynomials in the variable s^μ for 0<μ<1.As an application of this, in the case r(s)=1 and degp=degq=1, families of H_∞-stabilizing controllers are given and a complete parametrization of all H_∞-stabilizing controllers is obtained when .     

On multidimensional analogs of Melvin’s solution for classical series of Lie algebras

A multidimensional generalization of Melvin’s solution for an arbitrary simple Lie algebra is presented. The gravitational model contains n 2-forms and l ≥ n scalar fields, where n is the rank of . The solution is governed by a set of n functions obeying n ordinary differential equations with certain boundary conditions. It was conjectured earlier that these functions should be polynomials (the so-called fluxbrane polynomials). A program (in Maple) for calculating these polynomials for classical series of Lie algebras is suggested. The polynomials corresponding to the Lie algebra D ₄ are obtained. It is conjectured that the polynomials for A _n -, B _n - and C _n -series may be obtained from polynomials for D _n+1-series by using certain reduction formulas. Talk given at the International Conference RUSGRAV-13, June 23–28, 2008, PRUR, Moscow.     

Proof complexity in algebraic systems and bounded depth Frege systems with modular counting

We prove a lower bound of the formN ⁽¹⁾ on the degree of polynomials in a Nullstellensatz refutation of theCount _q polynomials over _m , whereq is a prime not dividingm. In addition, we give an explicit construction of a degreeN ⁽¹⁾ design for theCount _q principle over _m . As a corollary, using Beameet al. (1994) we obtain a lower bound of the form 2 ^N(1) for the number of formulas in a constant-depth Frege proof of the modular counting principleCount _q ^N from instances of the counting principleCount _m ^M .We discuss the polynomial calculus proof system and give a method of converting tree-like polynomial calculus derivations into low degree Nullstellensatz derivations.Further we shwo that a lower bound for proofs in a bounded depth Frege system in the language with the modular counting connectiveMOD _p follows from a lower bound on the degree of Nullstellensatz proofs with a constant number of levels of extension axioms, where the extension axioms comprise a formalization of the approximation method of Razborov (1987) and Smolensky (1987) (in fact, these two proof systems are basically equivalent).     

Polynomial enumeration of multidimensional lattices

Denoting the nonnegative (resp. signed) integers byN (resp.Z) and the real numbers byR, letK R ^m andf: R ^m R. Thenf is astoring function (resp.packing function) onK wheneverf|(Z ^m K) is an injection into (resp. bijection onto)N. Unit translations g_m of some P. Chowla [1961] polynomials are packing functions on the correspondingN ^m , and all compositions of these polynomials yield further packing functions on variousN ^r . We study this accessible family of packing functions, using standard properties ofordered trees to classify all those compositions, up to a simple equivalence, which define polynomial packing functions on eachN ^m . The numberc(m) of equivalence classes is an exponentially growing function for largem, whence the uniqueness conjecture of our prior two-dimensional work has no counterpart for largerm. We obtain the admissible degrees for composition polynomials inm variables; we describe the tre structures for all such polynomials with extremal degrees. Them-variable polynomials of least degree form a rather irregular numbera(m) of equivalence classes. Density considerations give some degree constraints on ageneral polynomial packing function whose domainK is the topological closure of a nonvoid open cone.     

New Sequences with Zero Autocorrelation

New families of unimodular sequences of length p = 3f + 1 with zero autocorrelation are described, p being a prime. The construction is based on employing Gauss periods. It is shown that in this case elements of the sequences are algebraic numbers defined by irreducible polynomials over of degree 12 (for the first family) and 6 (for the second family). In turn, these polynomials are factorized in some extension of the field into polynomials of degree, respectively, 4 and 2, which are written explicitly. For p = 13, using the exhaustive search method, full classification of unimodular sequences with zero autocorrelation is given.     

Stability analysis of sampled-data systems via open-/closed-loop characteristic polynomials contraposition

In this paper, a class of sampled-data systems with double feedbacks are scrutinized for internal/external stability through the open-/closed-loop characteristic polynomials contraposition. A sampled-data system with double feedbacks consists of a continuous-time plant and two feedback control loops: a discrete-time one for digital control objectives with sampler and zero-order hold synchronized, and a continuous-time one for analog control performances. Contraposition stability criteria are worked out by exploiting what we call the contraposition return difference relationship in between the open- and closed-loop characteristic polynomials defined via the lifted model. The criteria for asymptotical stability are necessary and sufficient, independent of open-loop poles distribution of the lifted model and locus orientation specification. Moreover, the criteria for L_p-stability are sufficient, while retaining the technical merits of the criteria for asymptotical stability. All criteria present stability conditions in the standard discrete-time sense that are implementable either graphically with loci plotting, or numerically without loci plotting. Examples are included to illustrate the results.     

Rational index of Vector Addition Systems languages

Summary The rational index _L of a non-empty language L is a function of into , whose asymptotic behavior can be used to classify languages. We prove that the languages associated to Vector Addition System or Petri nets have rational indexes bounded by polynomials. This situation should be contrasted with the case of context-free languages. Indeed some context-free languages like the Greibach's languages have rational indexes bounded by polynomials. But some other context-free languages have rational indexes in exp n and the generators of the rational cone of context-free languages have rational indexes in exp n ²/ln n. We give an upper bound and a lower bound on the rational index of each term of an infinite sequence of V.A.S. languages, such that any V.A.S. language can be obtained as the image by a rational transduction of one of these languages.     

Sparse shape functions for tetrahedral <Emphasis Type="Italic">p</Emphasis>-FEM using integrated Jacobi polynomials

Summary In this paper, we investigate the discretization of an elliptic boundary value problem in 3D by means of the hp-version of the finite element method using a mesh of tetrahedrons. We present several bases based on integrated Jacobi polynomials in which the element stiffness matrix has nonzero entries, where p denotes the polynomial degree. The proof of the sparsity requires the assistance of computer algebra software. Several numerical experiments show the efficiency of the proposed bases for higher polynomial degrees p.      

A generalized Euclidean algorithm for geometry theorem proving

In the first part of this paper, we present an algorithm that computes an unmixed-dimensional decomposition of a varietyV. EachV _i in the decompositionV=V ₁U...UV _m is given by a finite set of polynomials which represents the generic points of the irreducible components ofV _i . The basic operation in our algorithm is the computation of greatest common divisors of univariate polynomials over extension fields given by regular chains. No factorization is needed. In the second part, this algorithm is applied to geometry theorem proving. We show that it can be used for deciding whether geometry statements are generically true or whether they are true under given nondegeneracy conditions. If a geometry statement is generically true, the simplest nondegeneracy condition with respect to a lexicographical degree ordering can be constructed by means of our algorithm.This work was supported by the Austrian Fonds zur Förderung der wissenschaftlichen Forschung, project no. P6763, the Austrian Ministry of Science, project ESPRIT BRA 3125 MEDLAR, and the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C-0027.     

Some Ergodic Results on Stochastic Iterative Discrete Events Systems

This paper deals with the asymptotic behavior of the stochastic dynamics of discrete event systems. In this paper we focus on a wide class of models arising in several fields and particularly in computer science. This class of models may be characterized by stochastic recurrence equations in ^K of the form T(n+1) = _n+1(T(n)) where _n is a random operator monotone and 1—linear. We establish that the behaviour of the extremas of the process T(n) are linear. The results are an application of the sub-additive ergodic theorem of Kingman. We also give some stability properties of such sequences and a simple method of estimating the limit points.     

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.     

Calculation of associated functions for rational modified weight functions

Let be a sequence of polynomials orthogonal with respect to a measure dω on the real line and the sequence of their associated functions (they are essentially the Hilbert transforms of these polynomials). We show how to get associated functions Q _n ^[m,l] if the measure dω changes to , where Φ_m and ϕ _l are polynomials of degree m resp.l. The results can be used for example to construct Gaussian quadrature rules for rational modified weight functions.