# zbMATH — the first resource for mathematics

Restricted branching programs and their computational power. (English) Zbl 0747.68018
Mathematical foundations of computer science, Proc. 15th Symp., MFCS ’90, Banská Bystrica/Czech. 1990, Lect. Notes Comput. Sci. 452, 61-75 (1990).
[For the entire collection see Zbl 0731.00026.]
The article is, an overview of results characterizing the computational power of branching programs of several types, such as: $$\Omega$$-branching programs introduced by the author [Proc. STACS ’88, Lect. Notes Comp. Sci. 294, 81-90 (1988; Zbl 0644.68074)], $$\Omega$$- decision trees, read- once-only, obvious branching programs and $$\Omega$$-branching programs with bounded width.

##### MSC:
 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q05 Models of computation (Turing machines, etc.) (MSC2010)
##### Keywords:
$$\Omega$$-branching programs; decision trees