Control of discrete-event systems with partial observations using coalgebra and coinduction. (English) Zbl 1101.93050
Summary: Control of discrete-event systems with partial observations is treated by concepts and results of coalgebra and coinduction. Coalgebra is part of abstract algebra and enables a generalization of the computer science concept of bisimulation. It can be applied to automata theory and then provides a powerful algebraic tool to treat problems of supervisory control. A framework for control of discrete-event systems with partial observations is formulated in terms of coalgebra. The contributions to control theory are besides the framework, algorithms for supremal normal and supremal normal and controllable sublanguages of the plant.
Software:
UMDESReferences:
| [1] | Aczel, P. Non-Well-Founded Sets. CSLI Lecture Notes, Number 14, Stanford University, 1988. · Zbl 0668.04001 |
| [2] | Aczel, P., and Mendler, N. 1989. A final coalgebra theorem. In D. H. Pitt, D. E. Ryeheard, P. Dybjer, A. M. Pitts and A. Poigne (eds.), Proc. Category Theory and Computer Science, Lecture Notes in Computer Science, Volume 389, pp. 357–365. |
| [3] | Barrett, G., and Lafortune, S. 1998. Bisimulation, the supervisory control problem and strong model matching for finite state machines. J. Discret. Event Dyn. Syst.: Theory Appl. 8(4): 377–429. · Zbl 0919.93005 · doi:10.1023/A:1008301317459 |
| [4] | Bergeron, A. 1993. A unified approach to control problems in discrete event processes. Inform. Théor. Appl. 27(6): 555–573. · Zbl 0807.93002 |
| [5] | Brandt, R. D., Garg, V., Kumar, R., Lin, F., Marcus, S. I., and Wonham, W. M. 1990. Formulas for calculating supremal controllable and normal sublanguages. Syst. Control Lett. 15: 111–117. · Zbl 0715.93044 · doi:10.1016/0167-6911(90)90004-E |
| [6] | Cassandras, S. G., and Lafortune, S. 1999. Introduction to Discrete Event Systems. Dordrecht: Kluwer Academic Publishers. · Zbl 0934.93001 |
| [7] | Cieslak, R., Desclaux, C., Fawaz, A., and Varayia, P. 1988. Supervisory control of a class of discrete event processes. IEEE Trans. Automat. Contr. 33: 249–260. · Zbl 0639.93041 · doi:10.1109/9.402 |
| [8] | Cho, H., and Marcus, S. I. 1989a. On supremal languages of classes of sublanguages that arise in supervisor synthesis problems with partial observations. Math. Control Signal Syst. 2: 47–69. · Zbl 0654.93046 · doi:10.1007/BF02551361 |
| [9] | Cho, H., and Marcus, S. I. 1989b. Supremal and maximal sublanguages arising in supervisor synthesis problems with partial observations. Math. Syst. Theory 22: 171–211. · Zbl 0683.68062 |
| [10] | Eilenberg, S. 1974. Automata, Languages, and Machines. New York: Academic Press. · Zbl 0317.94045 |
| [11] | Eilenberg, S., and Moore, J. C. 1965. Adjoint functors and triples. Ill. J. Math. 9: 381–398. · Zbl 0135.02103 |
| [12] | Grossman, R., and Larson, R. G. 1992. The realization map of input–output maps using bialgebras. Forum Math. 4: 109–121. · Zbl 0754.16021 · doi:10.1515/form.1992.4.109 |
| [13] | Gumm, H. P. 2003. State based systems are coalgebras. Cubo–Matemática Educacional 5(2): 239–262. · Zbl 1074.18001 |
| [14] | Hopcroft, J. E., and Ullman, J. D. 1979. Introduction to Automata Theory, Languages and Computation. Reading, MA: Addison-Wesley. · Zbl 0426.68001 |
| [15] | Jacobson, N. 1980. Basic Algebra, Volume 2. New York: W. H. Freeman and Company. · Zbl 0441.16001 |
| [16] | Komenda, J. 2002a. Computation of supremal sublanguages of supervisory control using coalgebra. In Proceedings WODES’02, Workshop on Discrete-Event Systems, Zaragoza, October 2–4, pp. 26–33. |
| [17] | Komenda, J. 2002b. Coalgebra and supervisory control of discrete-event systems with partial observations. In Proceedings of MTNS 2002, Notre Dame (IN), August. |
| [18] | Komenda, J., and van Schuppen, J. H. 2003. Decentralized supervisory control with coalgebra. In Proceedings European Control Conference, ECC’03, Cambridge, September 1–4, 2003, only CD-ROM. Also appeared as Research Report CWI, MAS-E0310, ISSN 1386-3703, Amsterdam. |
| [19] | Komenda, J., and van Schuppen, J. H. 2004. Supremal normal sublanguages of large distributed discrete-event systems. In Proceedings WODES’04, Workshop on Discrete-Event Systems, Reims, September 22–24. |
| [20] | Lafortune, S., and Chen, E. 1990. The infimal closed and controllable superlanguage and its applications in supervisory control. IEEE Trans. Automat. Contr. 35(4): 398–405. · Zbl 0709.68028 · doi:10.1109/9.52291 |
| [21] | Lin, F., and Wonham, W. M. 1988. On observability of discrete-event systems. Inf. Sci. 44: 173–198. · Zbl 0644.93008 · doi:10.1016/0020-0255(88)90001-1 |
| [22] | Lin, F., and Wonham, W. M. 1990. Decentralized control and coordination of discrete-event systems with partial observations. IEEE Trans. Automat. Contr. 35: 1330–1337. · Zbl 0723.93043 · doi:10.1109/9.61009 |
| [23] | Milner, R. 1989a. A complete aximatisation for observational congruence of finite-state behaviors. Inf. Comput. 81: 227–247. · Zbl 0688.68050 · doi:10.1016/0890-5401(89)90070-9 |
| [24] | Milner, R. 1989b. Communication and Concurrency. Prentice Hall International Series in Computer Science. New York: Prentice Hall International. |
| [25] | Overkamp, A., and van Schuppen, J. H. 2000. Maximal solutions in decentralized supervisory control. SIAM J. Control Optim. 39(2): 492–511. · Zbl 0963.93056 · doi:10.1137/S0363012997321139 |
| [26] | Park, D.M.R. Concurrency and Automata on Infinite Sequences, volume 104 of LNCS. Springer, 1980. |
| [27] | Ramadge, P. J., and Wonham, W. M. 1989. The control of discrete-event systems. Proc. IEEE 77: 81–98. · doi:10.1109/5.21072 |
| [28] | Rudie, K., and Wonham, W. M. 1990. The infimal prefix-closed and observable superlanguage of a given language. Syst. Control Lett. 15: 361–371. · Zbl 0746.93061 · doi:10.1016/0167-6911(90)90059-4 |
| [29] | Rudie, K., and Wonham, W. M. 1992. Think globally, act locally: Decentralized supervisory control. IEEE Trans. Automat. Contr. 37(11): 1692–1708. · Zbl 0778.93002 · doi:10.1109/9.173140 |
| [30] | Rutten, J. J. M. M. 1998. Automata and Coinduction (An Exercise in Coalgebra). Research Report CWI, SEN-R9803, Amsterdam, May. Available also at http://www.cwi.nl/\(\sim\)janr. · Zbl 0940.68085 |
| [31] | Rutten, J. J. M. M. 1999. Coalgebra, Concurrency, and Control. Research Report CWI, SEN-R9921, Amsterdam, November. Available also at http://www.cwi.nl/\(\sim\)janr. · Zbl 1017.93064 |
| [32] | Rutten, J. J. M. M. 2000. Universal coalgebra: A theory of systems. Theor. Comp. Sci. 249(1): 3–80. · Zbl 0951.68038 · doi:10.1016/S0304-3975(00)00056-6 |
| [33] | Rutten, J. J. M. M. 2003. Fundamental study. Behavioural differential equations: A coinductive calculus of streams, automata, and power series. Theor. Comp. Sci. 308(1): 1–53. · Zbl 1071.68050 · doi:10.1016/S0304-3975(02)00895-2 |
| [34] | Sipser, M. 1997. Introduction to the Theory of Computation. Boston: PWS Publishing Company. · Zbl 1169.68300 |
| [35] | Takai, S., and Ushio, T. 2002. Effective computation of an Lm(G)-closed, controllable, and observable sublanguage arising in supervisory control. In Proceedings WODES’02, Workshop on Discrete-Event Systems, Zaragoza, October 2–4, pp. 34–39. · Zbl 1157.93444 |
| [36] | Tarski, A. 1955. A lattice-theoretical fixpoint theorem and its applications. Pac. J. Math. 5: 285–309. · Zbl 0064.26004 |
| [37] | Thistle, J. G. 1996. Supervisory control of discrete event systems. Math. Comput. Model. 11/12: 25–53. · Zbl 0854.93005 · doi:10.1016/0895-7177(96)00063-5 |
| [38] | Thistle, J. G., and Wonham, W. M. 1994. Supervision of infinite behavior of discrete-event systems. SIAM J. Control Optim. 32(4): 1098–1113. · Zbl 0925.93234 · doi:10.1137/S0363012991217524 |
| [39] | Tsitsiklis, J. N. 1989. On the control of discrete-event dynamical systems. Math. Control Signals Syst. 95–107. · Zbl 0677.93045 |
| [40] | Wonham, W. M. 1976. Towards an abstract internal model principle. IEEE Trans. Syst. Man Cybern. 6(11): 735–740. · Zbl 0341.93003 · doi:10.1109/TSMC.1976.4309444 |
| [41] | Wonham, W. M., and Ramadge, P. J. 1987. On the supremal controllable sublanguage of a given language. SIAM J. Control Optim. 25: 637–659. · doi:10.1137/0325036 |
| [42] | Yoo, T. S., and Lafortune, S. 2002. General architecture for decentralized supervisory control of discrete-event systems. Discret. Event Dyn. Syst.: Theory Appl. 12: 335–377. · Zbl 1048.93067 · doi:10.1023/A:1015625600613 |
| [43] | Yoo, T. S., Lafortune, S., and Lin, F. 2001. A uniform approach for computing supremal sublanguages arising in supervisory control theory. Preprint, Dept. of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
