×

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)