Le test d’identification d’état d’un système à événement discret (SED) a pour but d’en identifier l’état final, lorsque son état initial est inconnu. Une solution classique à ce problème, en supposant que le SED n’ait pas de sorties observables, consiste à déterminer une séquences de synchronisation, c.à-d., une séquence d’événements d’entrée qui conduit le SED sur un état connu. Ce problème a été résolu dans les années 60’ à l’aide des automates. L’objectif principal de cette thèse est d’utiliser les réseaux de Petri (RdP) pour obtenir une résolution plus optimal de ce problème et pour une plus large classe de systèmes.Initialement, nous montrons que la méthode classique peut être aisément étendue aux RdP synchronisés. Pour cette classe de réseaux non-autonomes, toute transition est associée à un événement d’entrée.L’approche proposée est générale, dans la mesure où elle s’applique à des RdP bornés arbitraires. Cependant, elle engendre le problème d’explosion combinatoire du nombre d’états. Pour obtenir des meilleures solutions, nous considérons une classe spéciale de RdP : les graphes d’état (GdE). Pour ces réseaux, nous considérons d’abord les GdE fortement connexes et proposons des approches pour la construction de SS, qui exploitent les propriétés structurelles du réseau en évitant ainsi une énumération exhaustive de l’espace d’état. Ces résultats s’étendent aux GdE non fortement connexes et à tout RdP synchronisé composé de GdE. Enfin, nous considérons la classe des RdP non bornés et proposons des séquences qui synchronisent le marquage des places non bornées. Une boîte à outils fournit toutes les approches décrites et est appliquée à des différents bancs d’essai. / State-identification experiments are designed to identify the final state of a discrete event system (DES) when its initial state is unknown. A classical solution, assuming the DES has no observable outputs, consists in determining a synchronizing sequence (SS), i.e., a sequence of input events that drives the system to a known state. This problem was essentially solved in the 60’ using automata. The main objective of this thesis is to use Petri nets (PNs) for solving the state-identification problem more efficiently and for a wider class of systems.We start showing that the classical SS construction method based on automata can be easily applied to synchronized PNs, a class of non-autonomous nets where each transition is associated with an input event. The proposed approach is fairly general and it works for arbitrary bounded nets with a complexity that is polynomial with the size of the state space. However, it incurs in the state-space explosion problem.Looking for more efficient solutions, we begin by considering a subclass of PNs called state machines (SMs). We first consider strongly connected SMs and propose a framework for SS construction that exploits structural criteria, not requiring an exhaustive enumeration of the state space of the net. Results are further extended to larger classes of nets, namely non strongly connected SMs and nets containing SM subnets. Finally we consider the class of unbounded nets that describe infinite state systems: even in this case we are able to compute sequences to synchronize the marking of bounded places. A Matlab toolbox implementing all approaches previously described has been designed and applied to a series of benchmarks.

L'un des problèmes fondamentaux de test pour les systèmes à événements discrets (SEDs) est l'identification d'un état final, c'est-à-dire, étant donné un système dont l'état courant est inconnu, trouver une séquence d'événements d'entrée pouvant le conduire à un état connu. Les séquences de synchronisation (SS), sans information de sortie, sont une solution classique à ce problème. Dans cette thèse, nous étudions la détermination des SS pour des systèmes modélisés par des réseaux de Petri synchronisés (SynPN) non bornés, une classe de réseaux de Petri avec des entrées. Dans la première partie de cette thèse, nous développons deux méthodes: 1) construction d'une représentation finie, appelée improved modified coverability graph (IMCG), pour d'écrire exactement l'espace d'états infini d'un 1-place-unbounded SynPN; 2) conversion d'un 1-place-unbounded SynPN en un automate pondéré (WA) fini et sauf équivalent. Les deux graphes sont ainsi potentiellement des outils puissants pour déterminer les SS pour une telle sous-classe de réseaux de Petri. Dans la seconde partie de cette thèse, nous développons des algorithmes de calcul pour deux problèmes de synchronisation de localisation dans le cas où l'IMCG ou le WA sont déterministes : synchronisation sur un seul nœud et synchronisation sur un sous-ensemble de nœuds de ces deux graphes. L'avantage de ces algorithmes de calcul est de réduire le calcul sur les graphes globaux (IMCG ou WA) à celui du plus petit sous-graphe: la composante fortement connectée ergodique peut réduire l'effort de calcul mais peut également être appliquée lorsque le IMCG ou le WA équivalent déterministes ne sont pas fortement connexes / One of the fundamental testing problems for discrete event systems (DESs) is the identification of a final state, i.e., given a system whose current state is unknown, find an input sequence that can drive it to a known state. Synchronizing sequences (SSs), without output information, are one conventional solution to this problem. In this thesis, we address the computation of SSs for systems modeled by unbounded synchronized Petri nets (SynPNs), a class of Petri nets with inputs. In the first part of this thesis, we utilize two methods: 1) construct a finite representation, called improved modified coverability graph (IMCG), to exactly describe the infinite state space of a 1-place-unbounded SynPN; 2) convert a 1-place-unbounded SynPN into an equivalent finite location weighted automaton (WA) with safety conditions. Both graphs are thus, potentially, useful tools to compute SSs for such subclass of nets. In the second part of this thesis, we develop computation algorithms for two location synchronization problems in the case either the IMCG or the WA is deterministic: synchronization into a single node and synchronization into a subset of nodes of these two graphs. The advantage of these computation algorithms consists in reducing the computation on the global graphs (IMCGs or WAs) to the one on the smaller subgraph: the ergodic strongly connected component (SCC), which can reduce the computational effort and furthermore can also be applied when the converted deterministic IMCG or WA is not strongly connected