Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Angluin D (1982) Inference of reversible languages. J ACM 29(3):741–765
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
Badouel E, Darondeau P (1996) On the synthesis of general petri nets. Technical Report 3025
Badouel E, Darondeau P (1998) Theory of regions. In: Lecture Notes in Computer Science: Lectures on Petri Nets I: Basic Models, 1491:529–586
Bemporad A, Morari M (1999) Control of systems integrating logic, dynamics and constraints. Automatica 35(3):407–429
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
Burkard RE, Rendl F (1991) Lexicographic bottleneck problems. Oper Res Lett 10:303–308
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
Cortadella J, Kishinevsky M, Lavagno L, Yakovlev A (1998) Deriving Petri nets from finite transition systems. IEEE Trans Comput 47(8):859–882
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
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
Gold EM (1978) Complexity of automaton identification from given data. Inf Control 37(3):302–320
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
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
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
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
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
Murata T (1989) Petri nets: properties, analysis and applications. Proceedings of the IEEE, 77(4):541–580, April 1989
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
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
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
van Schuppen JH (2004) System theory for system identification. J Econom 118(1–2):313–339, January–February 2004
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cabasino, M.P., Giua, A. & Seatzu, C. Identification of Petri Nets from Knowledge of Their Language. Discrete Event Dyn Syst 17, 447–474 (2007). https://doi.org/10.1007/s10626-007-0025-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10626-007-0025-0