×

zbMATH — the first resource for mathematics

Identification of Petri nets from knowledge of their language. (English) Zbl 1125.93332
Summary: In this paper we deal with the problem of identifying a Petri net system, given a finite language generated by it. First we consider the problem of identifying a free labeled Petri net system, i.e., all transition labels are distinct. The set of transitions and the number of places is assumed to be known, while the net structure and the initial marking are computed solving an integer programming problem. Then we extend this approach in several ways introducing additional information about the model (structural constraints, conservative components, stationary sequences) or about its initial marking. We also treat the problem of synthesizing a bounded net system starting from an automaton that generates its language. Finally, we show how the approach can also be generalized to the case of labeled Petri nets, where two or more transitions may share the same label. In particular, in this case we impose that the resulting net system is deterministic. In both cases the identification problem can still be solved via an integer programming problem.

MSC:
93B30 System identification
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
90C10 Integer programming
93C55 Discrete-time control/observation systems
PDF BibTeX Cite
Full Text: DOI
References:
[1] Angluin D (1982) Inference of reversible languages. J ACM 29(3):741–765 · Zbl 0485.68066
[2] Badouel E, Bernardinello L, Darondeau P (1995) Polynomial algorithms for the synthesis of bounded nets. In: Proceedings of CAAP’95, Lecture Notes in Computer Science. 915:647–679 · Zbl 0831.68067
[3] Badouel E, Darondeau P (1996) On the synthesis of general petri nets. Technical Report 3025 · Zbl 1101.68691
[4] Badouel E, Darondeau P (1998) Theory of regions. In: Lecture Notes in Computer Science: Lectures on Petri Nets I: Basic Models, 1491:529–586 · Zbl 0926.68088
[5] Bemporad A, Morari M (1999) Control of systems integrating logic, dynamics and constraints. Automatica 35(3):407–429 · Zbl 1049.93514
[6] Bourdeaud’huy T, Yim P (2004) Synthèse de réseaux de Petri à partir d’exigences. In: Actes de la 5me conf. francophone de Modélisation et Simulation, Nantes, France, pp 413–420, September 2004
[7] Burkard RE, Rendl F (1991) Lexicographic bottleneck problems. Oper Res Lett 10:303–308 · Zbl 0744.90069
[8] Cabasino MP, Giua A, Seatzu C (2006) Identification of deterministic Petri nets. In: Proceedings WODES’06: 8th Work on Discrete Event Systems, Ann-Arbor, MI, USA, July 2006
[9] Cortadella J, Kishinevsky M, Lavagno L, Yakovlev A (1998) Deriving Petri nets from finite transition systems. IEEE Trans Comput 47(8):859–882
[10] Dotoli M, Fanti MP, Mangini AM (2006) An optimization approach for identification of Petri nets. In: Proceedings IFAC WODES’06: 8th Work on Discrete Event Systems, Ann-Arbor, MI, USA, July 2006
[11] Giua A, Seatzu C (2005) Identification of free-labeled Petri nets via integer programming. In: Proceedings 44th IEEE Conf on Decision and Control, Seville, Spain, December 2005 · Zbl 1071.93028
[12] Gold EM (1978) Complexity of automaton identification from given data. Inf Control 37(3):302–320 · Zbl 0376.68041
[13] Hiraishi K (1992) Construction of a class of safe Petri nets by presenting firing sequences. In: Jensen K (ed) Lecture Notes in Computer Science; 13th International Conference on Application and Theory of Petri Nets 1992, Sheffield, UK, vol 616. Springer, pp 244–262, June 1992
[14] Li L, Ru Y, Hadjicostis CN (2006) Least-cost firing sequence estimation in labeled Petri nets. In: Proceedings 45th IEEE Conf on Decision and Control, San Diego, California USA, December 2006
[15] Lorenz R, Juhás G (2006) Towards synthesis of Petri nets from scenarios. In: Proceedings of 27th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, Turku, Finland, pp 302–321 · Zbl 1217.68152
[16] Meda-Campaña ME, López-Mellado E (2002) Incremental synthesis of Petri net models for identification of discrete event systems. In: Proceedings 41th IEEE Conf on Decision and Control, pp 805–810, Las Vegas, NV, USA, December 2002
[17] Meda-Campaña ME, López-Mellado E (2003) Required event sequences for identification of discrete event systems. In: Proceedings 42th IEEE Conf on Decision and Control, pp 3778–3783, Maui, HI, USA, December 2003
[18] Murata T (1989) Petri nets: properties, analysis and applications. Proceedings of the IEEE, 77(4):541–580, April 1989
[19] Reveliotis SA, Choi JY (2006) Designing reversibility-enforcing supervisors of polynomial complexity for bounded Petri nets through the theory of regions. In: Proceedings of 27th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, Turku, Finland, pp 322–341 · Zbl 1234.68306
[20] Ru Y, Hadjicostis CN (2006) State estimation in discrete event systems modeled by labeled Petri nets. In: Proceedings 45th IEEE Conf on Decision and Control, San Diego, CA, USA, December 2006
[21] Sreenivas RS (2002) On minimal representations of Petri net languages. In: Proceedings WODES’02: 6th Work on Discrete Event Systems, Zaragoza, Spain, pp 237–242, October 2002
[22] van Schuppen JH (2004) System theory for system identification. J Econom 118(1–2):313–339, January–February 2004 · Zbl 1033.93015
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.