Abstract FR:

Nous présentons, dans cette thèse, des résultats de complexité pour les problèmes de vérification (l'accessibilité, la couverture, le boundedness, la rationalité, la vivacité, l'inclusion et l'équivalence) de certaines classes de réseaux de Petri (réseaux cycliques, structurellement cycliques et réversibles). Ces résultats nous permettent de dériver d'autres résultats de complexité dans le domaine de l'algorithmique des variétés algébriques (semi groupes commutatifs). Nous calculons aussi des bornes supérieures pour les solutions minimales des systèmes diophantiens linéaires ce qui nous permet de montrer que le problème de l'accessibilité pour deux classes de réseaux de Petri (réseaux conservatifs et réseaux acycliques) est en espace 2#c#. #n.