Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\). (Russian. English original) Zbl 0797.68075
Kibern. Sb., Nov. Ser. 28, 94-113 (1991); translation from J. Comput. Syst. Sci. 38, No. 1, 150-164 (1989).
See the review in Zbl 0667.68059.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q45 | Formal languages and automata |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
