Monday , May 16 2022

An Efficient Testing for the Detection of Trajectories in
Discrete-Event Systems Modelled by S-Nets

ITESO University,
Periferico Sur # 8585, Tlaquepaque, 45604, Mexico,

* Corresponding author

Abstract: This paper addresses the problem of the detection of sequences of event executed in a Discrete-Event System modelled by Petri Nets. The nets are equipped with output symbols that an external observer is allowed to detect. To provide efficient solutions, the focus of this work is a subclass of nets called S-Systems. The construction of the Sequence-Detectability table leads to a necessary and sufficient condition for the characterization of the sequence detection in the case of safe nets. The safeness requirement is relaxed and its implication on the sequence detection is analyzed. Moreover, the utility of the sequence detectability in the analysis of the observability of the net is studied. An example illustrates the concepts and main results of this paper.

Keywords: Discrete-Event Systems, System Trajectories, Sequence-Detection, Petri Nets, Observability, S-systems.

>>Full text
An Efficient Testing for the Detection of Trajectories in Discrete-Event Systems Modelled by S-Nets, Studies in Informatics and Control, ISSN 1220-1766, vol. 25(3), pp. 363-374, 2016.

1. Introduction

The detection of the trajectories in a system is important for several purposes. For example, in Discrete-Event Systems (DES) some control schemes and observer designs use the sequence of events as feedback, while several techniques for the failure detection employ the system trajectories to establish a suitable recovery point [13], [16], [18], [19], [22].

Several approaches reported in the literature dealing with the formal analysis of DES have studied the system trajectories as part of other problems. For instance, the design of controllers, observers, trackers and detectors for DES have all been studied within the automaton field [10], [15], [19], [20], [21].

Petri nets (PN’s) have also been used for the analysis of almost the same problems as in the automaton framework. For example, the modeling of manufacturing systems, the supervisory control, state feedback schemes, sequence detection and the observability of PN’s and the design of controllers and observers, have been reported in [1], [5], [6], [7], [9], [11], [16].

Previous related work of the authors of this paper is also reported in the literature. In [2], a technique that allows controlling a DES using a supervisor with the feedback provided by an observer of sequences is developed. In [3], preliminary results for addressing the sequence detection of a subclass of PN, called Free-Choice nets, are provided.

This paper extends the previous research of the authors and provides novel results and efficient algorithms addressing the problem of the sequence detection in DES that are modelled by S-Systems, a subclass of PN with well-defined structure, where efficient solutions are derived. Firstly, safe nets are considered. For this case, the construction of the Sequence-Detectability table provides a necessary and sufficient condition for the testing of the sequence-detectability. Secondly, the safeness requirement is relaxed and its implication on the Sequence-Detectability is analyzed. For the non-safe case, the construction of the Event-Detectability table provides a necessary and sufficient condition for the verification of the property. Finally, the relationship among the sequence-detectability and the observability of S-Systems is outlined.

The rest of this paper is organized as follows. Section 2 introduces some basic PN’s notions used in this work. Section 3 presents the Sequence-Detectability property and its characterization in well-formed S-Systems. Section 4 outlines how the sequence-detectability supports solving the observability of the net. Section 5 provides the conclusions of this work and a final section shows the bibliographical references.


  1. CAMPOS-RODRIGUEZ, R., M. ALCARAZ-MEJIA, A Matlab/Simulink Framework for the Design of Controllers and Observers for Discrete-Event Systems, Journal of Electronics and Electrical Engineering, vol. 99(3), 2010, pp. 63-68.
  2. CAMPOS-RODRIGUEZ, R., M. ALCARAZ-MEJIA, J. MIRELES-GARCIA, Supervisory Control of Discrete Event Systems Using Observers, Proc. of the IEEE Mediterranean Conference on Control and Automation, vol. 1, 2007, pp. 1-7.
  3. CAMPOS-RODRIGUEZ, R., A. RAMIREZ-TREVINO, E. LOPEZ-MELLADO, Observability Analysis of Free-Choice Petri Net Models, Proceedings of IEEE/SMC Conference on Systems of Systems Engineering 6, 2006,
    pp. 77-82.
  1. DESEL, J., J. ESPARZA, Free Choice Petri Nets, Cambridge Univ. Press,
  2. GIUA, A., C. SEATZU, Observability of Place / Transition Nets, IEEE Transactions on Automatic Control, vol. 47(9), 2002, 1424-1437.
  3. GIUA, A., C. SEATZU, F. BASILE, Observer-based State-feedback Control of Timed Petri Nets with Deadlock Recovery, IEEE Transaction on Automatic Control, vol. 49(1), 2004, pp. 17-29.
  4. HERNANDEZ-MARTINEZ, E. G., E. S. PUGA-VELAZQUEZ, S. A. FOYO-VALDES, J. A. MEDA-CAMPANA, Modeling Framework for Automated Manufacturing Systems Based on Petri Nets and ISA Standards, Studies in Informatics and Control, vol. 22 (2), 2013, 163-174.
  5. HOPCROFT, J. E., R. MOTWANI, J. D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley,
  6. KAMMOUN, M. A., N. REZG, Z. ACHOUR, S. REZIG, State Space Search for Safe Time Petri Nets Based on Binary Decision Diagrams Tools: Application to Air Traffic Flow Management Problem, Studies in Informatics and Control, vol. 25(1), 2016, 39-50.
  7. KUMAR, R., M. A. SHAYMAN, Formulae Relating Controllability Observability and Co-observability, Automatica, 1998, pp. 211-215.
  8. MINCA, E., A New Approach for the Control Optimization of an Assembly/Disassembly Mechatronics Line Served by an Autonomous Robotic System, Studies in Informatics and Control, vol. 23 (1), 2014, pp. 13-22.
  9. MOODY, J. O., P. J. ANTSAKLIS, Petri Net Supervisors for DES with Uncontrollable and Unobservable Transitions, IEEE Transitions on Automatic Control, vol. 45(3), 2000, 462-476.
  10. MURATA, T., Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE, vol. 77(4), 1989, pp. 541-580.
  11. OZVEREN, C. M., A. S. WILLSKY, Observability of Discrete Event Dynamic Systems, IEEE Transactions on Automatic Control, vol. 35(7), 1990, pp. 797-806.
  12. OZVEREN, C. M., A. S. WILLSKY, Tracking and Restrictability in Discrete-event Dynamic Systems, SIAM Journal of Control and Optimisation, vol. 30(6), 1992, pp. 1423-1446.
  13. RIVERA-RANGEL, I., A. RAMÍREZ-TREVIÑO, L. AGUIRRE-SALAS, J. RUIZ-LEON, Geometrical Characterization of Observability in Interpreted Petri Nets, Kybernetika, vol. 41(5), 2005, pp. 553-574.
  14. SHU, S., F. LIN, H. YING, Detectability of Discrete Event Systems, IEEE Transactions on Automatic Control, vol. 52(12), 2007, pp. 2356-2359.
  15. SHU, S., F. LIN, Detectability for Discrete Event Systems with Dynamic Event Observation, System Control Letters, vol. 59(1), 2010, pp. 9-17.
  16. SHU, S., F. LIN, I-Detectability of Discrete-Event Systems, IEEE Transactions of Automatic Science and Engineering, vol. 10(1), 2013, pp. 187-196.
  17. TAKAI, S., T. USHIO, S. KODAMA, Static-state Feedback Control of Discrete-event Systems under Partial Observation, IEEE Transaction on Automatic Control, vol. 40(11), 1995, 1950-1954.
  18. WONG, K. C., W. M. WONHAM, On the Computation of Observers in Discrete-Event Systems, Discrete Event Dynamic Systems, vol. 14(1), 2004, pp. 55-107.