Restricted branching programs and their computational power. (English) Zbl 0747.68018

Meinel, Christoph

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.

Reviewer: G.B.Marandzhyan (Erevan)

MSC:

68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q05	Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

\(\Omega\)-branching programs; decision trees

Citations:

Zbl 0731.00026; Zbl 0644.68074