1
$\begingroup$

Consider a DAG $g$ as a label $l$ with a list of sub-nodes $\bar{g}$:

$g ::= l \enspace \bar{g}$

This is an "unfolded" representation of the DAG, i.e. it contains double entries, when two paths reach the same node.

When $g = l \enspace (l_1 \enspace \bar{g_1}, \ldots, l_n \enspace \bar{g_n})$ is ordered-complete, i.e.

$\bar{g_1} = (l_2 \enspace \bar{g_2}, \ldots, l_n \enspace \bar{g_n})$

$\bar{g_2} = (l_3 \enspace \bar{g_3}, \ldots, l_n \enspace \bar{g_n})$

$\ldots$

It can be represented as a list:

$ g \equiv l \enspace l_1 \ldots l_n $

This is, of course, a somewhat more efficient representation (in-memory, sharing the sub-lists wouldn't be that costly) but first of all this is a much more concise notation. I have to write some such graphs where this is a common pattern and I wonder if there is a name for this kind of compression. Also, is there a generalization of this compression?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I don't understand what your first sentence is trying to say or the intended meaning of your notation. You establish a grammar for DAGs, but how does that relate to the DAGs we usually know? What does $l$ represent? That looks more like a grammar for a tree, not a DAG. Can you give an example of a DAG and how you'd express it in your notation? $\endgroup$
    – D.W. ♦
    Jun 16 '16 at 16:17
  • $\begingroup$ It is the tree you get when you explore the DAG - basically a functional language representation of the DAG. $\endgroup$
    – choeger
    Jun 16 '16 at 17:57
  • 1
    $\begingroup$ Explore how? Are you assuming the DAG has only a single source/sink? What do the labels represent? I'm still not getting it: an example might help. $\endgroup$
    – D.W. ♦
    Jun 16 '16 at 18:07
  • 2
    $\begingroup$ Why does $g$ represent both graphs and subnodes? What's a subnode? $\endgroup$
    – Dave Clarke
    Jun 16 '16 at 18:31

Your Answer

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

Browse other questions tagged or ask your own question.