Firstly, we consider an example in order to get a feel for the problem, and to motivate the formality that follows. We return to the example illustrated in fig. 1.1. Here we have 3 directions a,b,c, two of which commute a,b. We require to take any path and convert it to a unique normalised form. Intuitively, we would like to take the left-most path of the many routes that lead to a particular node. Consider wanting to normalise the path abaacabba. Clearly, the commutativity requires that we can swap around any two adjacent ab or ba pairs, but in these situations a decision has to be made which one will be considered normalised. To resolve this we put an order on the directions, which for this example reduces to the rule that, wherever possible, as should be placed before bs. In the above path, since neither a nor b commute with c, there are two separate sections, divided by a c. So we can order the as and bs independently within these sections. This leads us to the normalised path aaabcaabb.
In a more general case, normalising a whole path at once will not need to be done, as we will be only ever be creating paths incrementally, so we need only consider the problem of adding directions one at a time to an already normalised path. So now consider adding an a to the above normalised version of our example, aaabcaabb. Since it commutes with all of the directions past the c in the middle, we could put it anywhere in the second half. We want to place it where it minimises the path name, so we insert it before a symbol it is less than, in this case before the two bs at the end. This results in the path aaabcaaabb.
We now want to formalise the intuitive ideas described above.