Normalisation using Markov algorithms

Markov algorithms are systems with an ordered set of string rewriting rules. Given an input string s, the algorithm searches through the set, and when a rule is matched then s is updated to s' by applying the rule. This procedure is repeated on s' by returning to the first rule. The loop is terminated either when the process is blocked (i.e. no rules can be applied), or when one of a set of marked termination rules is applied. In our case, we accept blocking as termination and ignore the use of explicit termination rules. Markov algorithms have been chosen because:-

• They are sufficiently powerful to describe all string processing algorithms.
• The example data structures considered so far can be simply expressed using them.
• The commuting/inverse family of structures can have their Markov normalising algorithms automatically generated from their specifications.

As mentioned above, we can generate the Markov algorithm for the path normalisation automatically, given the list of the commuting and inverse directions. Consider a simple example where we have three directions $\{a,b,c\}$, their inverses $\{a^{-1}, b^{-1}, c^{-1}\}$,and directions a and b commute (the algorithm is given in figure 2). The `+' and `-' are auxiliary symbols which are not in the language of the data structure, and mark the two phases of the algorithm. The algorithm assumes that the path name which is being normalised is of the form p+x, where p is an already normalised path name and x is the new direction being added. It actually finds the minimum path with respect to an order derived from an ordering on the alphabet D, identical to the concept of a geodesic , see [6].

 

Figure 2:  Markov Algorithm for the example commuting/inverse structure

The set of rules can be built automatically from the description of the commuting directions in the following way. For each direction a we add the following set of rules:-

We then append two extra rules: to switch between the two phases of the algorithm and to remove the `-' symbol at the end of the normalisation.