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?
Compression of a complete Directed Acylcic Graph
graph theory;graphs;data compression;dag