Le problème de l'accessibilité dans les réseaux de Pétri
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
We present a new proof of the decidability of the reachability for Petri nets improving those of Mayr and Kosaraju. We suppressed the calculation in Presburger's arithmetic and obtain new results in petri net and Petri net language theories. The first chapter is assigned to the resolution of linear systems of equations in positive integers. The three following chapters present the proof of the decidability of the reachability. In the last chapter we study the consequences of this result in Petri net language theory.
Abstract FR:
Nous donnons une nouvelle preuve de la décidabilité de l'accessibilité dans les réseaux de Petri améliorant celles de Mayr et de Kosaraju. Nous avons supprimé les calculs dans l'arithmétique de Presburger et obtenons de nouveaux résultats en théorie des réseaux de Petri et des langages de réseau de Petri. Un premier chapitre est consacré à la résolution des systèmes d'équations en nombres entiers positifs. Les trois chapitres suivants présentent la preuve de la décidabilité de l'accessibilité. Le dernier chapitre étudie les conséquences du résultat en théorie des langages de réseau de Petri.