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

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?

• You could write down all possible three-letter strings, and draw an arrow from one to another if it represents one of the above three transformations (so from $ABC$ draw an arrow to $ACC$, one to $BBC$ and one to $AAC$, but not to $ABB$, and not to $BCC$). Then your distance is exactly the distance known from the theory of directed graphs. Commented Apr 9, 2016 at 9:29
• Sure, I had considered that. I was wondering if there was a name for graph distance in the context of rewriting
– k_g
Commented Apr 9, 2016 at 9:30
• Not that I'm aware of. Commented Apr 9, 2016 at 9:31
• propositional-calculus was definitely not right. We don't seem to have a rewriting-systems tag, but I've added some other tags in that general vicinity. Commented Apr 9, 2016 at 9:31
• @HenningMakholm thanks, those seem much closer. I know that propositional-calculus involves rewriting, so I thought I'd tag it like that.
– k_g
Commented Apr 9, 2016 at 9:34