Is there a concept of distance between number of steps needed to move from one step to another?

41 Views Asked by At

Let's say that we have a set of rewrite rules:

$$AB \mapsto AC, A \mapsto B, B \mapsto A$$

Given the two strings $ABC$ and $BCC$

we know we can rewrite

$$ABC \mapsto ACC \mapsto BCC$$

We can define the minimum number of steps it takes for a rewrite from $S_1$ to $S_2$ to be $s(S_1, S_2)$. For example, $s(ABC, BCC) = 2$.

Is there a name for this distance?