Confluent rewriting system

Definition

A rewriting system is said to be confluent if whenever $u⟶v$ and $u⟶w$ are multi-step reductions in the rewriting system, then there exists a word $z$ such that there exist multi-step reductions $v⟶z$ and $w⟶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

• Strongly confluent rewriting system
• Complete rewriting system

Weaker properties

• Locally confluent rewriting system

Metaproperties

Free product-closedness

This property of a rewriting system is free product-closed. In other words, if we have two rewriting systems satisfying the property, the natural free product of these rewriting systems also satisfies the property

A free product of confluent rewriting systems is confluent. This is essentially because reductions in the various free factors do not interfere with one another, and hence commute.