I'm doing some machine learning research where I'm representing first order logic statements as Directed Acyclic Graphs (DAGs).

These DAGs all have a unique node which has no incoming edges. I have therefore been calling them "rooted DAGs."

I also care about the order of the incoming and outgoing edges from each node. (I need to know which node is the "first child" of a node. The ordering matters.) Therefore, I've been calling these "ordered rooted DAGs."

In general this idea could be extended to general graphs, although an adjacency matrix would no longer work to represent it. (adjacency lists would work still.)

Is there a name for this idea other than what I've used?

When I looked up "ordered graph" on Google, I find things about full or partial orders of all of the nodes of a graph, which is not the same thing.

Can you point to some good information on the subject?

  • $\begingroup$ Perhaps labeling each node would do the trick. Otherwise you'd have to find some quantifiable property that distinguishes children of a node from each other. But there may be cases where the graph has high symmetry, and multiple children may have identical properties. $\endgroup$
    – Graviton
    Aug 9, 2020 at 6:34
  • $\begingroup$ Also, I'm extremely curious, what method to you use to transform a FOL statement into a DAG? Coincidentally, I've been searching for such a thing. $\endgroup$
    – Graviton
    Aug 9, 2020 at 6:37
  • $\begingroup$ @Graviton I'm already labeling the Graph as well. (Each node is labeled with its corresponding symbol) A function in the formula is a node in the DAG which has directed edges to its arguments. If you can envision a tree, then just merge common subtrees and you get the DAG that I use. (Technically I'm using CNF and not full FOL also, but I work with people who do this on full FOL as well.) $\endgroup$
    – JacKeown
    Aug 9, 2020 at 13:49
  • $\begingroup$ The paper On DAG Languages and DAG Transducers | Drewes | Bulletin of EATCS (2017) seems to use the same terminology as you. $\endgroup$ Aug 9, 2020 at 20:43


You must log in to answer this question.

Browse other questions tagged .