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)
 Todo:
 Connections
 Todo:
 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 nonsink vertex is labelled by an input (variable?), and every such vertex has exactly p outgoing edges (labelled with the input values).
 Todo:
 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) ("ifthenelse") 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:

First we provide the "literals", that is, for each of the n inputs we provide its negation (by n negation gates).

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.

So c(e) is the boolean function which is true for a total assignment f iff f passes through e.

Now for the output gate we have two possibilities:

Either we consider the original 0sink, and connect all its ingoing edges to a norgate.

Or we consider the 1sink, and connect all its ingoing edges to an orgate.
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.

For the resulting circuit one should then perform the simplification which removes gates which don't have a connection to the output.

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.