Suppose we have a graph (A,->) consisting of a set of objects A and a binary relation -> on A. This is a simple case of an abstract reduction system, as defined in the Terese book (in the more general case, we have not just one relation ->, but an indexed set of relations). In the theory of abstract reduction systems, an element x is confluent iff whenever there is a path from x to y and a path from x to z, then there exists some element q which is reachable from both y and z. An element x is locally confluent iff whenever there is an edge (not an arbitrary path) from x to y and an edge from x to z, then there is some element q reachable from both y and z. So confluence implies local confluence, but (rather famously) the reverse implication holds only for terminating systems. An element is terminating iff there are no infinite paths from that element. An element is normalizing iff there exists a path from that element to a normal form, which is an element that has no outgoing edges. So terminating implies normalizing.

We have these four properties: confluence, local confluence, termination (sometimes also called strong normalization), and normalization (sometimes called weak normalization). What is the smallest graph that is property diverse, in the sense that for every consistent combination of properties, the graph contains an element with that combination of properties? (The consistency requirement for the set of properties for an element arises because confluence implies local confluence and termination implies normalization).

I will post the answer to this (with a nice picture) Monday…

### Like this:

Like Loading...

*Related*