BranchingPrograms.hpp File Reference

Plans regarding branching programs (for finite functions) More...

Go to the source code of this file.

Detailed Description

Plans regarding branching programs (for finite functions)

The notion of "branching program" (BP)
  • A source for many constructions is [Wegener 2000, Branching Programs and Binary Decision Diagrams].
  • It seems best to consider only one output here.
  • For p input values, q output values and n inputs (variables?) a branching program is a directed acyclic graph with exactly one source (designated), exactly q sinks (labelled with the output values), where every non-sink vertex is labelled by an input (variable?), and every such vertex has exactly p outgoing edges (labelled with the input values).
Translations into (boolean circuits):
  • First let's consider only boolean circuits; the task is, given a branching program P of type [n,2,2], construct a boolean circuit.
  • Theorem 2.1.3 in [Wegener 2000] yields a construction, using three circuits per node, by translating the ternary ite(x,y,z) ("if-then-else") into (x and y) or (not x and z), that is, using one binary disjunction, one binary conjunction, and one nonimplication.
  • Attractive seems to me the following construction:
    1. First we provide the "literals", that is, for each of the n inputs we provide its negation (by n negation gates).
    2. We introduce for each edge e in P a conjunction gate c(e), which has as inputs the incoming edges to the source of v plus the literal labelling e.
    3. So c(e) is the boolean function which is true for a total assignment f iff f passes through e.
    4. Now for the output gate we have two possibilities:
      • Either we consider the original 0-sink, and connect all its ingoing edges to a nor-gate.
      • Or we consider the 1-sink, and connect all its ingoing edges to an or-gate.
      These two possibilities reflect the double encoding of the output P(f) for a total assignment f: P(f) = 1 iff f doesn't reach 0 iff f reaches 1.
    5. For the resulting circuit one should then perform the simplification which removes gates which don't have a connection to the output.
    6. We have fewer gates, and we have a simple structure; the price for this is using or's and and's of higher arity, which seems harmless to me.

Definition in file BranchingPrograms.hpp.