Previous slide Next slide Back to the first slide View text version


A branching program is a rooted directed acyclic graph where each internal vertex is labelled by a variable name and for each input symbol there is a single edge leaving that vertex labelled by that symbol. The leaf vertices are labelled by ``Accept'' or ``Reject''. The machine proceeds along a root to leaf path by examining the input of the current vertex's label and then follows the edge corresponding to the value of that input. The machine accepts or rejects when it comes to the corresponding leaf vertex.