Approximating the Minimal Sensor Selection for Supervisory Control

• Arora S, Lund C (1997). Hardness of approximations. In: D S Hochbaum (ed) Algorithms for NP-Hard Problems. Boston, MA: PWS Publishing, pp 46–93.

  Google Scholar 

• Ausiello G, Crescenzi P, Gambosi G, Kahn V, Marchetti-Spaccamela A, Protasi M (1999). Complexity and Approximation Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, Berlin, Heidelberg.

  Google Scholar 

• Cassandras CG, Lafortune S (1999). Introduction to Discrete Event Systems. Boston, MA: Kluwer Academic Publishers.

  Google Scholar 

• Cho H (1990). Designing observation functions in supervisory control. In Proc. Korean Automatic Control Conference, pp 523–528.

• Garey MR, Johnson DS (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: W.H. Freeman.

  Google Scholar 

• Haji-Valizadeh A, Loparo KA (1996). Minimizing the cardinality of an events set for supervisors of discrete-event dynamical systems. IEEE Trans Automat Contr 41(11): 1579–1593.

  Article  MathSciNet  Google Scholar 

• Jiang S, Kumar R, Garcia HE (2003). Optimal sensor selection for discrete-event systems with partial observation. IEEE Trans Automat Contr 48(3):369–381.

  MathSciNet  Google Scholar 

• Khuller S, Kortsarz G, Rohloff K (2004, September). Approximating the minimal sensor selection for supervisory control. In Proc. 7th Workshop on Discrete Event Systems, Reims, France, pp 85–90

• Kortsarz G (2001). On the hardness of approximating spanners, Algorithmica, special Approx-98 issue, 30(3):432–450.

• Lin F, Wonham WM (1988). On observability of discrete-event systems. Inf Sci 44:173–198.

  MathSciNet  Google Scholar 

• Papadimitriou CH, Steiglitz K (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., Englewood Cliffs, NJ.

  Google Scholar 

• Ramadge PJ, Wonham WM (1987). Supervisory control of a class of discrete-event processes. SIAM J Control Optim 25(1):206–230.

  Article  MathSciNet  Google Scholar 

• Ramadge PJ, Wonham WM (1989). The control of discrete-event systems. Proc. IEEE 77(1):81–98.

  Article  Google Scholar 

• Raz R (1998). A parallel repetition theorem. SIAM J Comput 27(3):763–803.

  Article  MATH  MathSciNet  Google Scholar 

• Rohloff K (2004). Computations on Distributed Discrete-Event Systems. PhD thesis, The University of Michigan: Ann Arbor. Available at http://www.eecs.umich.edu/umdes.

• Rohloff K, van Schuppen JH (2004, December). Approximating the minimal-cost sensor-selection for discrete-event systems. Technical Report MASR0404, Centrum voor Wiskunde en Informatica (CWI), Amsterdam, the Netherlands.

• Rohloff K, van Schuppen JH (2005). Approximating minimal communicated event sets for decentralized supervisory control. In Proc. of the 16th IFAC World Congress.

• Rudie K, Willems JC (1995). The computational complexity of decentralized discrete-event control problems. IEEE Trans Automat Contr 40(7):1313–1318.

  Article  MathSciNet  Google Scholar 

• Tsitsiklis J (1989). On the control of discrete-event dynamical systems. MCCS Math Control Signals and Syst 2:95–107.

  MATH  MathSciNet  Google Scholar 

• Vazirani V (2001). Approximation Algorithms. Springer-Verlag, Berlin, Heidelberg.

  Google Scholar 

• Yoo T-S, Lafortune S (2002). NP-completeness of sensor selection problems arising in partially-observed discrete-event systems. IEEE Trans Automat Contr 47(9):1495–1499.

  MathSciNet  Google Scholar 

• Young S, Garg VK (1994, October). Optimal sensor and actuator choices for discrete event systems. In Proc. 31st Allerton Conference on Communication, Control, and Computing, pp 36.

Download references