In formal languages and automata theory, one of the first important results is the equivalence between deterministic finite automata and (formal) regular expressions. A DFA is just a labeled digraph with some extra information. I propose the following: (1) consider all states in the DAG to be accepting (2) label each arc with the label of the vertex where that arc begins (3) produce a regular expression for this DFA (choosing the topologically minimal states as starting states of distinct DFAs). First you'd want to topologically sort the vertices and then make one DFA/regular expression pair per connected component.
Example: node A goes to nodes B and C, B goes do D and E, C goes to E and F.
Topologically sorting finds the vertices in alphabetical order by label are already sorted: A, B, C, D, E. There is one connected component starting at the topologically minimal node A.
Going through the algorithm after labeling arcs might give you a regular expression like A(B(D+E)+C(E+F)).
Note that because the graphs are acyclic, you will never need the Kleene closure symbol asterisk/star. This answer could be elaborated on if there is interest.
EDIT: Some elaboration.
It was pointed out in the comments that there is some duplication in the above regular expression. This is true. However, this may not turn into catastrophic duplication: we can avoid duplicating subgraphs, at least to some degree. For instance, suppose there's a long subgraph with topologically minimal node E in the above example. Let's say it has acceptable regular expression r. Then we could adjust the above regular expression as follows: A((B+C)Er + BD + CF). There is still duplication, now between B and C rather than E, but because of the subgraph with topologically minimal node E, this is still a more concise representation.
Minimizing general regular expressions is PSPACE-complete. However, I don't know whether this bound applies to the minimization of regular expressions generated from DFAs whose graphs are DAGs. As the comments correctly note, the regular theory of DFAs and REs treats general digraphs, which are more complex than DAGs. It's entirely possible that regular expressions without the Kleene star might be easier to minimize than ones with it. This might be a question worth asking separately, possible on cs.stackexchange.com.
Another common way of representing DFAs is by using regular grammars. This is essentially equivalent to simply listing the ordered pairs of nodes corresponding to arcs in the DFA's state graph.
EDIT2: an example
Another answer had this example:
A->B
A->C
A->D
B->E
B->F
C->E
C->G
D->F
D->G
E->H
F->H
G->H
I suspect a nearly minimal regular expression as described here would be approximately the following: A(B(E+F)+C(E+G)+D(F+G))H. Our representation compares as follows:
- 24 symbols in grammar-equivalent, but 11 in regular expression
- 12 operators in grammar-equivalent, but 8 in regular expression
- 36 vs 19 total tokens
It's harder to compare to the visibility graph, since the representations are so different, but the regular expression clearly uses fewer total symbols (if we are counting symbols).
EDIT 3: another example was proposed, as follows:
a -> b
a -> c
a -> d
b -> c
b -> e
c -> f
d -> e
d -> f
d -> g
e -> f
e -> h
f -> i
g -> h
g -> i
h -> i
The most concise regular expression I could come up with by hand (second guess, no methodology) is this: a((b+d)e(f+h)+(bc+c+d)f+dg(h+#))i . Note the # is not part of the usual formal regular expression syntax and represents the empty regular expression, that is, it generates the language consisting of the empty string. This is a convenience to allow better minimzation and adds no computational power, only expressive. If you don't like it, you can use dgh + dh instead, it's only one symbol longer. This representation is still around half the size of the original grammar. Actually, the comparisons to both the grammar and the visibility graph are similar w.r.t. those of the last example.
EDIT 4: I will now expand the expression from the last example to show it is a factored representation of a disjoint union of paths through the DAG.
a((b+d)e(f+h)+(bc+c+d)f+dg(h+#))i
a((b+d)e(f+h)+(bc+c+d)f+dgh+dg)i
a((b+d)ef+(b+d)eh+(bc+c+d)f+dgh+dg)i
a(bef+def+beh+deh+(bc+c+d)f+dgh+dg)i
a(bef+def+beh+deh+bcf+cf+df+dgh+dg)i
abefi+adefi+abehi+adehi+abcfi+acfi+adfi+adghi+adgi
The raw textual representation would be to list all nodes and their connections– Maculation