ON SERIALIZABLE LANGUAGES
Mitsunori Ogihara · International Journal of Foundations of Computer Science · 1994
Cai and Furst introduced the notion of bottleneck Turing machines. Based on Barrington’s innovating technique, which is used to showed that polynomial-size branching programs have exactly the same power as NC1, Cai and Furst showed that the languages recognized by width-5 bottleneck Turing machines are exactly the same as those in PSPACE. In this paper, computational power of bottleneck Turing machines with widths fewer than 5 is investigated. It is shown that width-2 bottleneck Turing machines capture ⊕P// OptP , the class of sets recognized by ⊕P-machines with pre-computation in OptP. For languages recognized by bottleneck Turing machines with width-3 and width-4, some lower-bounds and upper-bounds are shown.