2
$\begingroup$

I'm reading a book on compilers, Engineering a Compiler, 2nd ed. by Keith D. Cooper & Linda Torczon and I came a across two new terms that I can't understand, they are:

transitive successor and transitive predecessor of a node $i$

I tried to find definitions of those online, but I'm having hard time with it. Everything I find talks about transitive reduction.

Can someone give a clear definition of this? Any help is appreciated.

$\endgroup$
1
$\begingroup$

If you ask Google with "transitive successor" (including the double quotes) you get several book references, and access to some pages (which I cannot read right now, because of a local problem). Considering that successor is a relation between the nodes of the directed graph, "transitive successor" should naturally be its transitive closure. One book is apparently using the term "direct successor" to be precise and avoid confusion with "transitive successor" which could occur when using "successor" alone.

$\endgroup$
1
$\begingroup$

Unfortunately I don't own your book, but I can conjecture what these terms mean.

In words, a transitive successor of $i$ is a successor of $i$, or a successor of a successor of $i$, or a successor of a successor of a successor of $i$, or ...

Here is a formal definition. We define an $n$-fold successor inductively:

  1. $i$ is the only $0$-fold successor of itself.

  2. $j$ is an $(n+1)$-fold successor of $i$ if $j$ is the $n$-fold successor of some successor $k$ of $i$.

For example, $j$ is a $1$-fold successor of $i$ iff it is a successor of $i$, and $j$ is a $2$-fold successor of $i$ if for some $k$, $j$ is a successor of $k$ and $k$ is a successor of $i$.

A transitive successor of $i$ is an $n$-fold successor of $i$ for some $n \geq 1$ (or perhaps $n \geq 0$, depending on your definition).

We can give an alternative definition using the language of directed graphs. Draw a graph in which there is an edge from $i$ to $j$ iff $j$ is a successor of $i$. A transitive successor of $i$ is then any vertex reachable from $i$, that is, any vertex $j$ such that there is some directed path from $i$ to $j$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.