display | more...
A decision diagram is a dag with exactly one source node (a node with no incoming edges).
Every node except sinks has a variable attached, the sinks have constants attached. Edges are usually marked with constants, too
A decision diagram represents a function f: D - > M, D,M sets ; the variables at the inner nodes represent the variables of the function, the constants are elements of M.
A decision diagram is evaluated in the following way:
  1. The evaluation is started at the source node.
  2. At every node in evaluation the value of the variable of the node is checked. Then the outgoing edge is choosen which has the value of the variable attached. The sink node of the edge becomes the new node in evaluation.
  3. This is repeated until a sink is reached.
  4. The value of the sink is returned.

In fact, there are more complicated versions, which have intervals or even additional functions attached to the edges or evaluate all outgoing edges, returning a function/value for every edge and combine the results by a fixed function.

The most important type are binary decision diagrams.
And decison trees are also decision diagrams.

Log in or register to write something here or to contact authors.