Confluence (informatique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Confluence.
image illustrant l’informatique
Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Le nom "confluence" est le même que celui utilisé en géographie ː deux cours d'eau se rejoignent.

En mathématiques, ou en informatique, la confluence d'une relation binaire est définie comme la propriété suivante :

Pour tous éléments tels que et , il existe un élément tel que et .

La confluence est équivalente à la propriété de Church-Rosser.

Confluence locale[modifier | modifier le code]

La confluence locale est une propriété plus faible que la confluence, utile pour les systèmes de réécriture. Elle est définie par ː

Pour tous éléments tels que et , il existe un élément tel que et .

Toute relation confluente est localement confluente mais une relation localement confluente n'est pas forcément confluente. Par exemple, la relation localement confluente A ← B ↔ C → D n'est pas confluente ː en effet A ← B → → D et il n'y a pas de E tel que A → E ← D.

Le lemme de Newman énonce qu'une relation qui termine et qui est localement confluente est confluente.

Voir aussi[modifier | modifier le code]

Lemme de Newman

Paire critique