Planar realizations of nonlinear davenport-schinzel sequences by segments

LetG={l ₁,...,l _n } be a collection ofn segments in the plane, none of which is vertical. Viewing them as the graphs of partially defined linear functions ofx, letY _G be their lower envelope (i.e., pointwise minimum).Y _G is a piecewise linear function, whose graph consists of subsegments of the segmentsl _i . Hart and Sharir [7] have shown thatY _G consists of at mostO(n(n)) segments (where(n) is the extremely slowly growing inverse Ackermann's function). We present here a construction of a setG ofn segments for whichY _G consists of(n(n)) subsegments, proving that the Hart-Sharir bound is tight in the worst case.Another interpretation of our result is in terms of Davenport-Schinzel sequences: the sequenceE _G of indices of segments inG in the order in which they appear alongY _G is a Davenport-Schinzel sequence of order 3, i.e., no two adjacent elements ofE _G are equal andE _G contains no subsequence of the forma ...b ...a ...b ...a. Hart and Sharir have shown that the maximal length of such a sequence composed ofn symbols is (n(n)). Our result shows that the lower bound construction of Hart and Sharir can be realized by the lower envelope ofn straight segments, thus settling one of the main open problems in this area.Work on this paper has been partially supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. This paper is part of the first author's M.Sc. thesis prepared at Tel Aviv University under the supervision of the second author. A preliminary version of this paper has appeared inProceedings of the 27th IEEE Symposium on Foundations of Computer Science, Toronto, 97–106, 1986.     

Nonnegative realizations of systems over nonnegative quasi-fields

In this paper, several sufficient conditions of nonnegative realizability of nonnegative systems have been derived. The authors have also pointed out the relation between two kinds of nonnegative realizability.The project supported by Natural Science Foundation of China.     

Minimal ideals of Jordan systems

We show that minimal ideals of Jordan systems (algebras, triple systems, and pairs) are either simple or trivial, so answering the question posed by Nam and McCrimmon in 1983. Mathematics Subject Classification (2000) 17C10, 17C20     

Explicit Hamiltonian realizations of non-degenerate three-dimensional real linear differential systems

The purpose of this work is to give explicit Hamiltonian realizations for all non-degenerate real three-dimensional linear differential systems.     

Minimal equivalence of differential IO systems

Differential algebraic controllability, observability, and minimalrealization are considered further, upon which a new equivalenceproblem, i.e. the minimal equivalence of two given differentialinput-output (IO) systems through state-space realization isconsidered. Some criteria for equivalence and minimal equivalenceof two IO systems are given. The algorithm for checking minimalequivalence of two IO systems with single input is implementedwith MACSYMA. Email: xyl{at}sun.engg.le.ac.uk David.Bell{at}umist.ac.uk     

Minimal polynomial systems for parametric matrices

In this article, we study the minimal polynomials of parametric matrices. Using the concept of (comprehensive) Gröbner systems for parametric ideals, we introduce the notion of a minimal polynomial system for a parametric matrix, i.e. we decompose the space of parameters into a finite set of cells and for each cell we give the corresponding minimal polynomial of the matrix. We also present an algorithm for computing a minimal polynomial system for a given parametric matrix.     

Minimal stabilizers for linear dynamical systems

Doklady Mathematics -     

Controllability of nonlinear systems

Some sufficient conditions are presented for the controllability of general nonlinear systems. First, the controllability problem is transformed into the problem of existence of fixed points for some operator; using Schauder's theorem, it is derived that a sufficient condition for controllability is the existence of a subsetS inC _n+m (T) which is invariant for a derived operator. Secondly, with the aid of the notion of comparison principle, the existence of the subsetS is guaranteed by the existence of solutions for some nonlinear integral inequality or equality equations. For example, one solution for such nonlinear integral equations is obtained under the assumption of the uniform boundedness for a nonlinear term of the differential equation.     

Observability of nonlinear systems

New necessary and sufficient conditions are presented for the observability of systems described by nonlinear ordinary differential equations with nonlinear observations. The conditions are based on extension of the necessary and sufficient conditions for observability of time-varying linear systems to the linearized trajectory of the nonlinear system. The result is that the local observability of any initial condition can be readily determined, and the observability of the entire initial domain can be computed. The observability of constant parameters appearing in the differential equations is also considered. Examples are presented to illustrate the theory.This research was supported by the National Science Foundation, Grant No. NSF GK-10136.     

Controllability of nonlinear systems

In this paper we obtain global controllability of a semilinear system involving monotone nonlinearities of both Lipschitzian and non-Lipschitzian types.     

Minimal system inverses for linear multivariable systems

The problem of minimal inverses for linear time invariant multivariable systems is formulated and constructively solved in a state space setting. Unknown initial states as well as zero initial states are considered. The spectrum of the minimal inverse is shown to be unique and constructable from the original system without first calculating the whole inverse. This leads to a simple way of introducing the equivalence of “zeros” in state space terminology.     

Optimal estimation of nonlinear state nonlinear observation systems

The concept of this work is that research on nonlinear modeling and estimation in a stochastic framework brings with it the study of the orthogonality structure of the probability densities involved. The connection is made by means of a probabilistic quantity, called the theta function, which under fairly broad integrability conditions defines the class of factorable random processes. These processes play a central role in the derivation of a recursive estimation scheme which is mathematically optimal and computationally attractive. The theory of factorable processes is simpler and its relevance to estimation practice is more direct than that of other sophisticated nonlinear approaches, such as martingales and Lie algebras.The author is indebted to Prof. D. R. Smith, University of California, San Diego, for helpful suggestions.