BACK TO INDEX

 Books and proceedings
1. E.D. Sontag. Polynomial Response Maps, volume 13 of Lecture Notes in Control and Information Sciences. Springer-Verlag, Berlin, 1979. [PDF] Keyword(s): realization theory, discrete-time, real algebraic geometry.
Abstract:
 (This is a monograph based upon Eduardo Sontag's Ph.D. thesis. The contents are basically the same as the thesis, except for a very few revisions and extensions.) This work deals the realization theory of discrete-time systems (with inputs and outputs, in the sense of control theory) defined by polynomial update equations. It is based upon the premise that the natural tools for the study of the structural-algebraic properties (in particular, realization theory) of polynomial input/output maps are provided by algebraic geometry and commutative algebra, perhaps as much as linear algebra provides the natural tools for studying linear systems. Basic ideas from algebraic geometry are used throughout in system-theoretic applications (Hilbert's basis theorem to finite-time observability, dimension theory to minimal realizations, Zariski's Main Theorem to uniqueness of canonical realizations, etc). In order to keep the level elementary (in particular, not utilizing sheaf-theoretic concepts), certain ideas like nonaffine varieties are used only implicitly (eg., quasi-affine as open sets in affine varieties) or in technical parts of a few proofs, and the terminology is similarly simplified (e.g., "polynomial map" instead of "scheme morphism restricted to k-points", or "k-space" instead of "k-points of an affine k-scheme").

 Articles in journal or book chapters
1. B. DasGupta and E.D. Sontag. A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems. Theor. Comput. Sci., 262(1-2):161-189, 2001. [PDF] [doi:http://dx.doi.org/10.1016/S0304-3975(00)00188-2] Keyword(s): hybrid systems, computational complexity.
Abstract:
 The area of hybrid systems concerns issues of modeling, computation, and control for systems which combine discrete and continuous components. The subclass of piecewise linear (PL) systems provides one systematic approach to discrete-time hybrid systems, naturally blending switching mechanisms with classical linear components. PL systems model arbitrary interconnections of finite automata and linear systems. Tools from automata theory, logic, and related areas of computer science and finite mathematics are used in the study of PL systems, in conjunction with linear algebra techniques, all in the context of a "PL algebra" formalism. PL systems are of interest as controllers as well as identification models. Basic questions for any class of systems are those of equivalence, and, in particular, if state spaces are equivalent under a change of variables. This paper studies this state-space equivalence problem for PL systems. The problem was known to be decidable, but its computational complexity was potentially exponential; here it is shown to be solvable in polynomial-time.

2. X. Bao, Z. Lin, and E.D. Sontag. Finite gain stabilization of discrete-time linear systems subject to actuator saturation. Automatica, 36(2):269-277, 2000. [PDF] Keyword(s): discrete-time, saturation, input-to-state stability, stabilization, ISS, bounded inputs.
Abstract:
 It is shown that, for neutrally stable discrete-time linear systems subject to actuator saturation, finite gain lp stabilization can be achieved by linear output feedback, for all p>1. An explicit construction of the corresponding feedback laws is given. The feedback laws constructed also result in a closed-loop system that is globally asymptotically stable, and in an input-to-state estimate.

3. D. Nesic, A.R. Teel, and E.D. Sontag. Formulas relating KL stability estimates of discrete-time and sampled-data nonlinear systems. Systems Control Lett., 38(1):49-60, 1999. [PDF] Keyword(s): input to state stability, sampled-data systems, discrete-time systems, sampling, ISS.
Abstract:
 We provide an explicit KL stability or input-to-state stability (ISS) estimate for a sampled-data nonlinear system in terms of the KL estimate for the corresponding discrete-time system and a K function describing inter-sample growth. It is quite obvious that a uniform inter-sample growth condition, plus an ISS property for the exact discrete-time model of a closed-loop system, implies uniform ISS of the sampled-data nonlinear system; our results serve to quantify these facts by means of comparison functions. Our results can be used as an alternative to prove and extend results of Aeyels et al and extend some results by Chen et al to a class of nonlinear systems. Finally, the formulas we establish can be used as a tool for some other problems which we indicate.

4. E.D. Sontag and F.R. Wirth. Remarks on universal nonsingular controls for discrete-time systems. Systems Control Lett., 33(2):81-88, 1998. [PDF] [doi:http://dx.doi.org/10.1016/S0167-6911(97)00117-5] Keyword(s): discrete time, controllability.
Abstract:
 For analytic discrete-time systems, it is shown that uniform forward accessibility implies the generic existence of universal nonsingular control sequences. A particular application is given by considering forward accessible systems on compact manifolds. For general systems, it is proved that the complement of the set of universal sequences of infinite length is of the first category. For classes of systems satisfying a descending chain condition, and in particular for systems defined by polynomial dynamics, forward accessibility implies uniform forward accessibility.

5. Y. Yang, E.D. Sontag, and H.J. Sussmann. Global stabilization of linear discrete-time systems with bounded feedback. Systems Control Lett., 30(5):273-281, 1997. [PDF] [doi:http://dx.doi.org/10.1016/S0167-6911(97)00021-2] Keyword(s): discrete-time, saturation, bounded inputs.
Abstract:
 This paper deals with the problem of global stabilization of linear discrete time systems by means of bounded feedback laws. The main result proved is an analog of one proved for the continuous time case by the authors, and shows that such stabilization is possible if and only if the system is stabilizable with arbitrary controls and the transition matrix has spectral radius less or equal to one. The proof provides in principle an algorithm for the construction of such feedback laws, which can be implemented either as cascades or as parallel connections (single hidden layer neural networks'') of simple saturation functions.

6. E.D. Sontag. Interconnected automata and linear systems: a theoretical framework in discrete-time. In R. Alur, T.A. Henzinger, and E.D. Sontag, editors, Proceedings of the DIMACS/SYCON workshop on Hybrid systems III : verification and control, pages 436-448. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1996. [PDF] Keyword(s): hybrid systems.
Abstract:
 This paper summarizes the definitions and several of the main results of an approach to hybrid systems, which combines finite automata and linear systems, developed by the author in the early 1980s. Some related more recent results are briefly mentioned as well.

7. Y. Wang and E.D. Sontag. Orders of input/output differential equations and state-space dimensions. SIAM J. Control Optim., 33(4):1102-1126, 1995. [PDF] [doi:http://dx.doi.org/10.1137/S0363012993246828] Keyword(s): identifiability, observability, realization theory.
Abstract:
 This paper deals with the orders of input/output equations satisfied by nonlinear systems. Such equations represent differential (or difference, in the discrete-time case) relations between high-order derivatives (or shifts, respectively) of input and output signals. It is shown that, under analyticity assumptions, there cannot exist equations of order less than the minimal dimension of any observable realization; this generalizes the known situation in the classical linear case. The results depend on new facts, themselves of considerable interest in control theory, regarding universal inputs for observability in the discrete case, and observation spaces in both the discrete and continuous cases. Included in the paper is also a new and simple self-contained proof of Sussmann's universal input theorem for continuous-time analytic systems.

8. F. Albertini and E.D. Sontag. Further results on controllability properties of discrete-time nonlinear systems. Dynam. Control, 4(3):235-253, 1994. [PDF] [doi:http://dx.doi.org/10.1007/BF01985073] Keyword(s): discrete-time, nonlinear control.
Abstract:
 Controllability questions for discrete-time nonlinear systems are addressed in this paper. In particular, we continue the search for conditions under which the group-like notion of transitivity implies the stronger and semigroup-like property of forward accessibility. We show that this implication holds, pointwise, for states which have a weak Poisson stability property, and globally, if there exists a global "attractor" for the system.

9. F. Albertini and E.D. Sontag. Discrete-time transitivity and accessibility: analytic systems. SIAM J. Control Optim., 31(6):1599-1622, 1993. [PDF] [doi:http://dx.doi.org/10.1137/0331075]
Abstract:
 A basic open question for discrete-time nonlinear systems is that of determining when, in analogy with the classical continuous-time "positive form of Chow's Lemma", accessibility follows from transitivity of a natural group action. This paper studies the problem, and establishes the desired implication for analytic systems in several cases: (i) compact state space, (ii) under a Poisson stability condition, and (iii) in a generic sense. In addition, the paper studies accessibility properties of the "control sets" recently introduced in the context of dynamical systems studies. Finally, various examples and counterexamples are provided relating the various Lie algebras introduced in past work.

10. R. Koplon and E.D. Sontag. Linear systems with sign-observations. SIAM J. Control Optim., 31(5):1245-1266, 1993. [PDF] [doi:http://dx.doi.org/10.1137/0331059] Keyword(s): observability.
Abstract:
 This paper deals with systems that are obtained from linear time-invariant continuous- or discrete-time devices followed by a function that just provides the sign of each output. Such systems appear naturally in the study of quantized observations as well as in signal processing and neural network theory. Results are given on observability, minimal realizations, and other system-theoretic concepts. Certain major differences exist with the linear case, and other results generalize in a surprisingly straightforward manner.

11. F. Albertini and E.D. Sontag. Transitivity and forward accessibility of discrete-time nonlinear systems. In Analysis of controlled dynamical systems (Lyon, 1990), volume 8 of Progr. Systems Control Theory, pages 21-34. Birkhäuser Boston, Boston, MA, 1991.

12. B. Jakubczyk and E.D. Sontag. Controllability of nonlinear discrete-time systems: a Lie-algebraic approach. SIAM J. Control Optim., 28(1):1-33, 1990. [PDF] [doi:http://dx.doi.org/10.1137/0328001] Keyword(s): discrete-time.
Abstract:
 This paper presents a geometric study of controllability for discrete-time nonlinear systems. Various accessibility properties are characterized in terms of Lie algebras of vector fields. Some of the results obtained are parallel to analogous ones in continuous-time, but in many respects the theory is substantially different and many new phenomena appear.

13. B. Jakubczyk and E.D. Sontag. Nonlinear discrete-time systems. Accessibility conditions. In Modern optimal control, volume 119 of Lecture Notes in Pure and Appl. Math., pages 173-185. Dekker, New York, 1989. [PDF]

14. A. Arapostathis, B. Jakubczyk, H.-G. Lee, S. I. Marcus, and E.D. Sontag. The effect of sampling on linear equivalence and feedback linearization. Systems Control Lett., 13(5):373-381, 1989. [PDF] [doi:http://dx.doi.org/10.1016/0167-6911(89)90103-5] Keyword(s): discrete-time, sampled-data systems, discrete-time systems, sampling.
Abstract:
 We investigate the effect of sampling on linearization for continuous time systems. It is shown that the discretized system is linearizable by state coordinate change for an open set of sampling times if and only if the continuous time system is linearizable by state coordinate change. Also, it is shown that linearizability via digital feedback imposes highly nongeneric constraints on the structure of the plant, even if this is known to be linearizable with continuous-time feedback.

15. E.D. Sontag. A Chow property for sampled bilinear systems. In C.I. Byrnes, C.F. Martin, and R. Saeks, editors, Analysis and Control of Nonlinear Systems, pages 205-211. North Holland, Amsterdam, 1988. [PDF] Keyword(s): discrete-time, bilinear systems.
Abstract:
 This paper studies accessibility (weak controllability) of bilinear systems under constant sampling rates. It is shown that the property is preserved provided that the sampling period satisfies a condition related to the eigenvalues of the autonomous dynamics matrix. This condition generalizes the classical Kalman-Ho-Narendra criterion which is well known in the linear case, and which, for observability, results in the classical Nyquist theorem.

16. E.D. Sontag. Reachability, observability, and realization of a class of discrete-time nonlinear systems. In Encycl. of Systems and Control, pages 3288-3293. Pergamon Press, 1987. Keyword(s): observability.

17. E.D. Sontag. An eigenvalue condition for sample weak controllability of bilinear systems. Systems Control Lett., 7(4):313-315, 1986. [PDF] [doi:http://dx.doi.org/10.1016/0167-6911(86)90045-9] Keyword(s): discrete-time.
Abstract:
 Weak controllability of bilinear systems is preserved under sampling provided that the sampling period satisfies a condition related to the eigenvalues of the autonomous dynamics matrix. This condition generalizes the classical Kalman-Ho-Narendra criterion which is well known in the linear case.

18. B.W. Dickinson and E.D. Sontag. Dynamic realizations of sufficient sequences. IEEE Trans. Inform. Theory, 31(5):670-676, 1985. [PDF] Keyword(s): realization theory, statistics, innovations, sufficient statistics.
Abstract:
 Let Ul, U2, ... be a sequence of observed random variables and (T1(U1),T2(Ul,U2),...) be a corresponding sequence of sufficient statistics (a sufficient sequence). Under certain regularity conditions, the sufficient sequence defines the input/output map of a time-varying, discrete-time nonlinear system. This system provides a recursive way of updating the sufficient statistic as new observations are made. Conditions are provided assuring that such a system evolves in a state space of minimal dimension. Several examples are provided to illustrate how this notion of dimensional minimality is related to other properties of sufficient sequences. The results can be used to verify the form of the minimum dimension (discrete-time) nonlinear filter associated with the autoregressive parameter estimation problem.

19. E.D. Sontag. On finitary linear systems. Kybernetika (Prague), 15(5):349-358, 1979. [PDF] Keyword(s): systems over rings.
Abstract:
 An abstract operator approach is introduced, permitting a unified study of discrete- and continuous-time linear control systems. As an application, an algorithm is given for deciding if a linear system can be built from any fixed set of linear components. Finally, a criterion is given for reachability of the abstract systems introduced, giving thus a unified proof of known reachability results for discrete-time, continuous-time, and delay-differential systems.

20. E.D. Sontag. Realization theory of discrete-time nonlinear systems. I. The bounded case. IEEE Trans. Circuits and Systems, 26(5):342-356, 1979. [PDF]
Abstract:
 A state-space realization theory is presented for a wide class of discrete time input/output behaviors. Although In many ways restricted, this class does include as particular cases those treated in the literature (linear, multilinear, internally bilinear, homogeneous), as well ss certain nonanalytic nonlinearities. The theory is conceptually simple, and matrix-theoretic algorithms are straightforward. Finite-realizability of these behaviors by state-affine systems is shown to be equivalent both to the existence of high-order input/output equadons and to realizability by more general types of systems.

21. E.D. Sontag and Y. Rouchaleau. On discrete-time polynomial systems. Nonlinear Anal., 1(1):55-64, 1976. [PDF] Keyword(s): identifiability, observability, polynomial systems, realization theory, discrete-time.
Abstract:
 Considered here are a type of discrete-time systems which have algebraic constraints on their state set and for which the state transitions are given by (arbitrary) polynomial functions of the inputs and state variables. The paper studies reachability in bounded time, the problem of deciding whether two systems have the same external behavior by applying finitely many inputs, the fact that finitely many inputs (which can be chosen quite arbitrarily) are sufficient to separate those states of a system which are distinguishable, and introduces the subject of realization theory for this class of systems.

 Conference articles
1. Z-P. Jiang, E.D. Sontag, and Y. Wang. Input-to-state stability for discrete-time nonlinear systems. In Proc. 14th IFAC World Congress, Vol E (Beijing), pages 277-282, 1999. [PDF] Keyword(s): input to state stability, input to state stability, ISS, discrete-time.
Abstract:
 This paper studies the input-to-state stability (ISS) property for discrete-time nonlinear systems. We show that many standard ISS results may be extended to the discrete-time case. More precisely, we provide a Lyapunov-like sufficient condition for ISS, and we show the equivalence between the ISS property and various other properties, as well as provide a small gain theorem.

2. D. Nesic, A.R. Teel, and E.D. Sontag. On stability and input-to-state stability ${\cal K}{\cal L}$ estimates of discrete-time and sampled-data nonlinear systems. In Proc. American Control Conf., San Diego, June 1999, pages 3990-3994, 1999. Keyword(s): input to state stability, sampled-data systems, discrete-time systems, sampling.

3. X. Bao, Z. Lin, and E.D. Sontag. Some new results on finite gain $l_p$ stabilization of discrete-time linear systems subject to actuator saturation. In Proc. IEEE Conf. Decision and Control, Tampa, Dec. 1998, IEEE Publications, 1998, pages 4628-4629, 1998. Keyword(s): saturation, bounded inputs.

4. F. Albertini and E.D. Sontag. Controllability of discrete-time nonlinear systems. In Systems and Networks: Mathematical Theory and Applications, Proc. MTNS '93, Vol. 2, Akad. Verlag, Regensburg, pages 35-38, 1993.

5. F. Albertini and E.D. Sontag. Identifiability of discrete-time neural networks. In Proc. European Control Conf., Groningen, June 1993, pages 460-465, 1993. Keyword(s): neural networks, recurrent neural networks.

6. F. Albertini and E.D. Sontag. Accessibility of discrete-time nonlinear systems, and some relations to chaotic dynamics. In Proc. Conf. Inform. Sci. and Systems, John Hopkins University, March 1991, pages 731-736, 1991.

7. E.D. Sontag and H.J. Sussmann. Accessibility under sampling. In Proc. IEEE Conf. Dec. and Control, Orlando, Dec. 1982, 1982. [PDF] Keyword(s): discrete-time.
Abstract:
 This note addresses the following problem: Find conditions under which a continuous-time (nonlinear) system gives rise, under constant rate sampling, to a discrete-time system which satisfies the accessibility property.

8. E.D. Sontag. Algebraic-geometric methods in the realization of discrete-time systems. In Proc. Conf. Inform. Sci. and Systems, John Hopkins Univ. (1978), pages 158-162, 1978.

 Internal reports
1. E.D. Sontag and F.R. Wirth. Remarks on universal nonsingular controls for discrete-time systems. Technical report 381, Institute for Dynamical Systems, University of Bremen, 1996.

BACK TO INDEX

Disclaimer:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders.