Skip to main content
SpringerLink
Log in

On the control of discrete-event dynamical systems

  • Published:
Mathematics of Control, Signals and Systems Aims and scope Submit manuscript

Abstract

We study a class of problems related to the supervisory control of a discrete-event system (DES), as formulated by Ramadge and Wonham, and we focus on the computational effort required for their solution. While the problem of supervisory control of a perfectly observed DES may be easily solved by dynamic programming, the problem becomes intractable (in the sense of complexity theory) when imperfectly observed systems are considered.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • [B] D. P. Bertsekas,Dynamic Programming and Stochastic Control, Academic Press, New York, 1976.

    MATH  Google Scholar 

  • [CDFV] R. Cieslak, C. Desclaux, A. Fawaz, and P. Varaiya, Supervisory control of discrete-event processes with partial observations,IEEE Trans. Automat. Control,33 (1988), 249–260.

    Article  MATH  Google Scholar 

  • [PS] C. H. Papadimitriou and K. Steiglitz,Combinatorial Opimization: Algorithms and Complexity, Prentice Hall, Englewood Cliffs, NJ, 1982.

    MATH  Google Scholar 

  • [PT] C. H. Papadimitriou and J. N. Tsitsiklis, The complexity of Markov decision processes,Math. Oper. Res.,12 (1987), 441–450.

    Article  MathSciNet  MATH  Google Scholar 

  • [P] C. P. Pfleeger, State reduction in incompletely specified finite-state machines,IEEE Trans. Comput.,22 (1973), 1099–1102.

    MathSciNet  MATH  Google Scholar 

  • [RW1] P. J. Ramadge and W. M. Wonham, Modular supervisory control of discrete event systems,Proceedings of the Seventh International Conference on the Analysis and Optimization of Systems, Antibes, June 25–27, 1986, pp. 202–214, Lecture Notes in Control and Optimization of Systems, Vol. 83 (A. Bensoussan and J. L. Lions, eds), Springer-Verlag, New York, 1986.

    Google Scholar 

  • [RW2] P. J. Ramadge and W. M. Wonham, Supervisory control of a class of discrete-event processes,SIAM J. Control Optim.,25 (1987), 206–230.

    Article  MathSciNet  MATH  Google Scholar 

  • [T] J. N. Tsitsiklis, On the Control of Discrete-event Dynamical Systems, Technical Report LIDS-P-1661, Laboratory for Information and Decision Systems, M.I.T., Cambridge, MA March 1987.

    Google Scholar 

  • [VW] A. F. Vaz and W. M. Wonham, On supervisor reduction in discrete-event systems.Internat. J. Control,44 (1986), 475–491.

    MathSciNet  MATH  Google Scholar 

  • [WR] W. M. Wonham and P. J. Ramadge, On the supremal controllable sublanguage of a given language,SIAM J. Control Optim.,25 (1987), 637–659.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Room 35-214, 02139, Cambridge, Massachusetts, U.S.A.

    John N. Tsitsiklis

Authors
  1. John N. Tsitsiklis
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research supported by the Army Research Office (Grant No. DAAL03-86-K-0171) and by an NSF PYI award, with matching funds from Bellcore Inc.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tsitsiklis, J.N. On the control of discrete-event dynamical systems. Math. Control Signal Systems 2, 95–107 (1989). https://doi.org/10.1007/BF02551817

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02551817

Key words

Search

Navigation