1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Arthur
    Commented Apr 9, 2016 at 9:29
  • $\begingroup$ Sure, I had considered that. I was wondering if there was a name for graph distance in the context of rewriting $\endgroup$
    – k_g
    Commented Apr 9, 2016 at 9:30
  • $\begingroup$ Not that I'm aware of. $\endgroup$
    – Arthur
    Commented Apr 9, 2016 at 9:31
  • $\begingroup$ 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. $\endgroup$
    – hmakholm left over Monica
    Commented Apr 9, 2016 at 9:31
  • $\begingroup$ @HenningMakholm thanks, those seem much closer. I know that propositional-calculus involves rewriting, so I thought I'd tag it like that. $\endgroup$
    – k_g
    Commented Apr 9, 2016 at 9:34

0

Reset to default

You must log in to answer this question.