Abstract FR:

Cette these s'inscrit dans le domaine de la theorie des traces. Apres une presentation generale de cette theorie, nous nous interessons aux automates paralleles qui permettent de caracteriser les langages de traces reconnaissables. Nous presentons une classe de reseaux de petri : les reseaux de petri saufs ; nous montrons que sous certaines conditions ces reseaux caracterisent la classe des langages de traces reconnaissables. Nous donnons une semantique de p-trace pour les reseaux qui ne verifient pas ces conditions. Puis dans les autres chapitres, nous nous interessons aux automates asynchrones. Les automates asynchrones finis sont aux langages de traces ce que les automates finis classiques sont aux langages de mots. Nous presentons une nouvelle construction des automates asynchrones. Cette construction fait intervenir des automates finis dits quasi-asynchrones qui sont des automates finis pouvant etre vus comme des versions sequentielles d'automates asynchrones. Nous traitons ensuite des questions de la determinisation et de la construction modulaire. Nous presentons un algorithme de determinisation pour les automates asynchrones projectifs. Les automates asynchrones projectifs forment une sous-classe des automates asynchrones qui contient strictement celle des automates asynchrones faiblement cooperants. Nous proposons egalement une construction modulaire des automates asynchrones. Puis nous relions les automates asynchrones et les reseaux de petri dans un cadre categorique. Nous definissons une notion de morphisme entre automates asynchrones les structurant en une categorie. Nos morphismes generalisent ceux definis par g. Pighizzini. Nous etablissons une coreflection entre les automates asynchrones et les reseaux de petri saufs, c'est a dire que nous pouvons considerer les automates asynchrones comme une sous-classe des reseaux de petri. Enfin le dernier chapitre etudie les liens entre automates asynchrones et les semantiques des processus concurrents introduites par milner (sccs et ses derivees).