Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

Question

I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism.

By ordered I mean that each vertex has a list of outgoing edges in fixed order and that order must be respected by the isomorphism. I don't know if there is a widely used name for such structures.

An equivalent problem is probably isomorphism of acyclic deterministic semiautomata (the ordering of the edges can be recovered by just fixing an order on the alphabet and listing the transitions for a state in that order).

If the DAG is restricted to have only one root, it is trivial (just order by left-to-right DFS). Or, for the automaton, if the automaton has a designated initial state and all other states must be reachable. But if that's not the case, I'm at a loss.

I don't see any obvious polynomial reductions from GI-complete problems that I am familiar with. My intuition tells me this looks like it should be in P.

The best algorithm I came up with so far tries to successively label the nodes with numbers from 1 to n in a canonical way by picking the ‘smallest’ root w.r.t. some suitable partial ordering (e.g. based on the number of children and the ordering numbers that have already been assigned), but when there are still several minimal roots, I don't see how to get around trying all permutations of them.

There is a paper on isomorphism of ‘ordered graphs’ that seems to be similar to my problem except that their graphs are undirected and their ‘ordering’ is not a list, but a cyclic list. My intuition would tell me that my problem can be reduced to this (e.g. by adding some conspicuous ‘list beginning marker’ to recover the list from the cyclic list) but I am not quite sure. I am also not sure if there is not something more direct than their approach for my case.

EDIT: I thought about it a bit more and I think their approach doesn't work for my case at all. In my setting, there is an ordering on the outgoing edges of each node, but not on the ingoing ones. That makes a huge difference.

For illustration, here are two instances of the problem:

Answer 1

If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex of $D$ and every arc of $D$. For every arc $u \rightarrow v$ of $D$, add the arcs: $uv \rightarrow u$ and $uv \rightarrow v$ in $D’$ (in this order). Clearly $D’$ is an (ordered) DAG and two digraphs $D_1$ and $D_2$ are isomorphic iff their corresponding ordered dags $D_1’$ and $D_2’$ are (ordered) isomorphic.

If you need to order both outgoing and incoming edges there is a simple polynomial time algorithm: if $D_1$ and $D_2$ are connected then fixing $f(u) = v$ (for $u \in V(D_1)$ and $v \in V(D_2)$) uniquely determines $f$.