The Problem

The directions available at each node are described by a set of symbols S. The commutativity is represented by a (commutative, not necessarily transitive) relation $\sim$ on S. A path P is a string of symbols from S, we use P[k] to denote the kth symbol from P.

In the situation where we allow directions to be on l different levels, we essentially have a path made up of l different sub paths. We can then consider the problem of normalising these l paths completely independently of each other. So we need not consider the multi-level problem, as it reduces in each level to a one level problem. So for the rest of the chapter we assume all directions are on the same level.

The set S also has a total order < described on it. We can extend this to a total order on paths by the lexicographic extension. This can be defined as in fig 3.1.

 

Figure 3.1:   Lexicographic ordering on paths