TESTING DISCRETE EVENT SYSTEMS: SYNCHRONIZING SEQUENCES USING PETRI NETS

In the field of Discrete Event Systems, an important class of testing problems consists in determining a final state after the execution of a test. This problem was completely solved in the 60's using homing and synchronizing sequences for finite state machines with inputs/outputs. In a synchronizing problem, we want to drive an implementation of a given model, seen as a black-box, to a, known state regardless of its initial state and the outputs. In this paper, we propose a first approach to solve the synchronizing problem. on systems represented by a class of synchronised Petri nets. We show that, regardless of the number of tokens that the net contains, a synchronizing sequence may be computed in terms of the net structure, thus avoiding the state explosion problem.