Testing experiments on bounded Petri nets

Synchronizing sequences have been proposed in the late 1960s to solve testing problems on systems modeled by finite-state machines. Such sequences lead a system, seen as a black box, from an unknown current state to a known final one. This paper presents a first investigation of the computation of synchronizing sequences for systems modeled by synchronized Petri nets. In the first part of the paper, existing techniques for automata are adapted to this new setting. Later on, new approaches, that exploit the net structure to efficiently compute synchronizing sequences without an exhaustive enumeration of the state space, are presented. Note to Practitioners: Driving a system to a known state when its current state is not known is a very important problem in many practical applications, such as checking communication protocols, part orienteers, digital reset circuit, etc. This topic has received a lot of attention in the past few decades. The classic approach to solve this problem considers systems modeled by automata. In particular, a standard technique requires the computation of a synchronizing sequence, i.e., a sequence of inputs that drives the system to a unique final state independently of the initial state and does not require the observation of the system's outputs. This paper presents a first investigation on the computation of synchronizing sequences for systems modeled by synchronized Petri nets. Petri nets are a very intuitive model that is widely used in automation. Many analysis problems can be efficiently solved using Petri nets by taking into account the net structure, without an exhaustive enumeration of its state space. The techniques we propose for computing synchronizing sequences exploit the net structure and lead to viable algorithms that can be applied to large scale systems.