# Compression of a complete Directed Acylcic Graph

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?

• 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?
– D.W.
Jun 16 '16 at 16:17
• It is the tree you get when you explore the DAG - basically a functional language representation of the DAG. Jun 16 '16 at 17:57
• 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.
– D.W.
Jun 16 '16 at 18:07
• Why does $g$ represent both graphs and subnodes? What's a subnode? Jun 16 '16 at 18:31