×

zbMATH — the first resource for mathematics

A comparative analysis of recent identification approaches for discrete-event systems. (English) Zbl 1205.93034
Summary: Analogous to the identification of continuous dynamical systems, identification of Discrete-Event Systems (DESs) consists of determining the mathematical model that describes the behaviour of a given ill-known or eventually unknown system from the observation of the evolution of its inputs and outputs. First, the paper overviews identification approaches of DES found in the literature, and then it provides a comparative analysis of three recent and innovative contributions.

MSC:
93B30 System identification
93C65 Discrete event control/observation systems
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] E. M. Gold, “Language identification in the limit,” Information and Control, vol. 10, no. 5, pp. 447-474, 1967. · Zbl 0259.68032
[2] M. E. Meda-Campaña, On-line identification of discrete event systems: fundamentals and algorithms for the synthesis of Petri net model, Ph.D. thesis, Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional, Unidad Guadalajara, Mexico, November 2002.
[3] S. Klein, L. Litz, and J.-J. Lesage, “Fault detection of discrete event systems using an identification approach,” in Proceedings of the 16th IFAC World Congress, p. 6, Praha, Czech Republic, July 2005, CDROM, paper no 02643.
[4] S. Klein, Identification of discrete event systems for fault detection purposes, Ph.D. thesis, Ecole Normale Supérieure de Cachan, Paris, France, October 2005.
[5] A. Giua and C. Seatzu, “Identification of free-labeled Petri nets via integer programming,” in Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference (CDC-ECC ’05), pp. 7639-7644, Seville, Spain, December 2005.
[6] M. P. Cabasino, A. Giua, and C. Seatzu, “Identification of deterministic Petri nets,” in Proceedings of the 8th International Workshop on Discrete Event Systems (WODES ’06), pp. 325-331, Ann Arbor, Mich, USA, July 2006. · Zbl 1125.93332
[7] M. Dotoli, M. P. Fanti, and A. M. Mangini, “Real time identification of discrete event systems using Petri nets,” Automatica, vol. 44, no. 5, pp. 1209-1219, 2008. · Zbl 1283.93187
[8] L. G. Valiant, “A theory of the learnable,” Communications of the ACM, vol. 27, no. 11, pp. 1134-1142, 1984. · Zbl 0587.68077
[9] D. Angluin, “Queries and concept learning,” Machine Learning, vol. 2, no. 4, pp. 319-342, 1988. · Zbl 0243.94039
[10] T. L. Booth, Sequential Machines and Automata Theory, John Wiley & Sons, New York, NY, USA, 1967. · Zbl 0165.02303
[11] J. Kella, “Sequential machine identification,” IEEE Transactions on Computers, vol. 20, no. 3, pp. 332-338, 1971. · Zbl 0218.94022
[12] A. W. Biermann and J. A. Feldman, “On the synthesis of finite-state machines from samples of their behavior,” IEEE Transactions on Computers, vol. 21, no. 6, pp. 592-597, 1972. · Zbl 0243.94039
[13] L. P. J. Veelenturf, “Inference of sequential machines from sample computations,” IEEE Transactions on Computers, vol. 27, no. 2, pp. 167-170, 1978. · Zbl 0368.94052
[14] L. P. J. Veelenturf, “An Automata-theoretical approach to developing learning neural networks,” Cybernetics and Systems, vol. 12, no. 1-2, pp. 179-202, 1981. · Zbl 0457.68048
[15] M. Richetin, M. Naranjo, and P. Luneau, “Identification of automata by sequential learning,” Pattern Recognition Letters, vol. 2, no. 6, pp. 379-385, 1984. · Zbl 0556.68018
[16] L. S. Levy and A. K. Joshi, “Skeletal structural descriptions,” Information and Control, vol. 39, no. 2, pp. 192-211, 1978. · Zbl 0387.68067
[17] H. Ishizaka, “Polynomial time learnability of simple deterministic languages,” Machine Learning, vol. 5, no. 2, pp. 151-164, 1990.
[18] Y. Takada, “Grammatical inference for even linear languages based on control sets,” Information Processing Letters, vol. 28, no. 4, pp. 193-199, 1988. · Zbl 0658.68094
[19] K. Hiraishi, “Construction of a class of safe Petri nets by presenting firing sequences,” in Proceedings of the 13th International Conference on Application and Theory of Petri Nets, vol. 616 of Lectures Notes in Computer Sciences, pp. 244-262, Sheffield, UK, June 1992.
[20] M. E. Meda-Campaña, “DES identification using interpreted Petri nets,” in Proceedings of the International Symposium on Robotics and Automation, pp. 353-357, Saltillo, Mexico, December 1998.
[21] M. E. Meda-Campaña, A. Ramírez-Treviño, and E. López-Mellado, “Asymptotic identification of discrete event systems,” in Proceedings of the 39th IEEE Confernce on Decision and Control, pp. 2266-2271, Sydney, Australia, December 2000.
[22] M. E. Meda-Campaña and E. López-Mellado, “A passive method for on-line identification of discrete event systems,” in Proceedings of the 40th IEEE Conference on Decision and Control (CDC ’01), pp. 4990-4995, Orlando, Fla, USA, December 2001.
[23] M. E. Meda-Campaña and E. López-Mellado, “Incremental synthesis of Petri nets models for identification of discrete event systems,” in Proceedings of the 41st IEEE Conference on Decision and Control, pp. 805-810, Las Vegas, Nev, USA, December 2002.
[24] M. E. Meda-Campaña and E. López-Mellado, “Required event sequences for identification of discrete event s ystems,” in Proceedings of the 42nd IEEE Conference on Decision and Control (CDC ’03), vol. 4, pp. 3778-3783, Maui, Hawaii, USA, December 2003.
[25] M. E. Meda-Campaña and E. López-Mellado, “Identification of concurrent discrete event systems using Petri nets,” in Proceedings of the 17th IMACS World Congress on Computational and Applied Mathematics, pp. 11-15, Paris, France, July 2005.
[26] M. Roth, J.-J. Lesage, and L. Litz, “Distributed identification of concurrent discrete event systems for fault detection purposes,” in Proceedings of the European Control Conference (ECC ’09), Budapest, Hungary, August 2009.
[27] M. Roth, J.-J. Lesage, and L. Litz, “Black-box identification of discrete event systems with optimal partitioning of concurrent subsystems,” in Proceedings of the American Control Conference (ACC ’10), Baltimore, Md, USA, June 2010.
[28] M. Roth, J.-J. Lesage, and L. Litz, “An FDI method for manufacturing systems based on an identified model,” in Proceedings of the 13h IFAC Symposium on Information Control Problems in Manufacturing (INCO ’09), pp. 1389-1394, Moscow, Russia, June 2009.
[29] M. P. Cabasino, A. Giua, and C. Seatzu, “Computational complexity analysis of a Petri net identification procedure,” in Proceedings of the International Symposium on Nonlinear Theory and Its Applications (NOLTA ’08), Bologna, Italy, September 2006. · Zbl 1304.93053
[30] M. P. Cabasino, A. Giua, and C. Seatzu, “Identification of unbounded Petri nets from their coverability graph,” in Proceedings of the 45th IEEE Conference on Decision and Control (CDC ’06), pp. 434-440, San Diego, Calif, USA, December 2006.
[31] M. Dotoli, M. P. Fanti, and A. M. Mangini, “An optimization approach for identification of Petri Nets,” in Proceedings of the 8th International Workshop on Discrete Event Systems (WODES ’06), pp. 332-337, Ann Arbor, Mich, USA, July 2006.
[32] M. Dotoli, M. P. Fanti, and A. M. Mangini, “On-line identification of discrete event systems: a case study,” in Proceedings of the IEEE International Conference on Automation Science and Engineering (CASE ’07), pp. 405-410, Shangai, China, October 2006.
[33] M. Dotoli, M. P. Fanti, and A. M. Mangini, “On line identification of discrete event systems via Petri nets: an application to monitor specification,” in Proceedings of the 3rd Annual IEEE International Conference on Automation Science and Engineering (CASE ’07), pp. 893-898, Scottsdale, Ariz, USA, September 2007.
[34] M. P. Fanti and C. Seatzu, “Fault diagnosis and identification of discrete event systems using Petri nets,” in Proceedings of the 9th International Workshop on Discrete Event Systems (WODES ’08), pp. 432-435, Göteborg, Sweden, May 2008.
[35] T. Moor, J. Raisch, and S. O’Young, “Supervisory control of hybrid systems via l-complete approximations,” in Proceedings of the 4th IEEE Workshop on Discrete Event Systems (WODES ’98), pp. 426-431, Cagliari, Italy, August 1998.
[36] A.P. Estrada-Vargas, E. López-Mellado, and J.-J. Lesage, “Off-line identification of concurrent discrete event systems exhibiting cyclic behaviour,” in Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, pp. 181-186, San Antonio Tex, USA, October 2009.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.