Bounded Width Branching Programs
We examine the branching program model of computation and in particular the classes of languages which can be recognized when the width of the programs is bounded by a constant. After slightly revising the framework of definitions to sharpen analogies with other models, we prove that width 5 polyno...
Main Author: | Barrington, David A. |
---|---|
Other Authors: | Sipser, Michael |
Published: |
2023
|
Online Access: | https://hdl.handle.net/1721.1/149629 |
Similar Items
-
Width-3 Permutation Branching Programs
by: Barrington, David A.
Published: (2023) -
Near-Optimal Derandomization of Medium-Width Branching Programs
by: Putterman, Aaron (Louie), et al.
Published: (2023) -
Bounds on Urysohn width
by: Balitskiy, Alexey
Published: (2022) -
Branch-and-bound strategies for dynamic programming
by: Morin, Thomas L., et al.
Published: (2009) -
Branch-and bound strategies for dynamic programming
by: Morin, Thomas L., et al.
Published: (2009)