Abstract FR:

Nous proposons un modele pour les programmes paralleles generalisant la theorie des traces. Deux actions a et b sont independantes dans certains contextes connus par une relation appelee relation d'independance locale (en abrege ril). Deux mots sont equivalents s'ils se deduisent l'un de l'autre par permutation d'actions independantes ; une classe d'equivalence est l'ensemble des executions sequentielles d'un meme processus parallele. Nous etudions les proprietes des rils en liaison avec les proprietes definies pour d'autres modeles (automates avec relations de concurrence de droste, equivalences distribuees de rozoy). Nous montrons que les classes d'equivalences sont representables par des multi-ensembles partiellement ordonnes (exprimant une causalite) si et seulement si la ril satisfait une propriete de stabilite ; notre modele est alors equivalent a d'autres modeles (ensembles cci de p-traces de arnold, structures d'evenements stables de winskel, certains reseaux de petri place/transition) ; les equivalences distribuees de rozoy sont obtenues en ajoutant une propriete supplementaire de coherence. Nous definissons les rils reconnaissables. Une ril stable est reconnaissable si et seulement si les classes d'equivalences sont les projections des classes d'un langage reconnaissable de traces ; nous donnons une nouvelle demonstration de ce theoreme de arnold. Nous proposons un modele d'automate fini asynchrone: l'etat de l'automate est reparti sur un ensemble de registres. A chaque action est associe, en fonction de l'etat global de l'automate, un domaine (sous-ensemble de registres) ; la fonction de transition modifie uniquement les registres du domaine. Ces automates generalisent les automates asynchrones pour les langages de traces introduits par zielonka. Une ril est associee naturellement a un automate asynchrone. Nous montrons que toute ril stable reconnaissable est la ril d'un automate asynchrone