Confluent rewriting system: Difference between revisions

Revision as of 15:20, 28 May 2007

Definition

A rewriting system is said to be confluent if whenever $u\to v$ and $u\to w$ are reductions in the rewriting system, then there exists a word $z$ such that there exist reductions $v\to z$ and $w\to z$ .

In other words, any two things from the same source finally get together again.

The term confluent rewriting system can also be used for a rewriting system for a group. Note that the free group rewriting system is confluent. A group that possesses a confluent rewriting system is termed a confluent group.

Relation with other properties

Stronger properties

Weaker properties

Locally confluent rewriting system

@@ Line 3: / Line 3: @@
 ==Definition==
-A [[rewriting system]] is said to be ''''confluent''' if whenever <math>u \to v</math> and <math>u \to w</math> are reductions in the rewriting system, then there exists a word <math>z</math> such that there exist reductions <math>v \to z</math> and <math>w \to z</math>.
+A [[rewriting system]] is said to be '''confluent''' if whenever <math>u \to v</math> and <math>u \to w</math> are reductions in the rewriting system, then there exists a word <math>z</math> such that there exist reductions <math>v \to z</math> and <math>w \to z</math>.
 In other words, any two things from the same source finally get together again.