1991/03/01 by Jin‐Yi Cai, Merrick L. Furst · 1 voice · 3 citations
Computer Science · #Algorithms and Data Compression #Logic, programming, and type systems #semigroups and automata theory
paper · doi:10.1142/s0129054191000054
openalex publication_date 1991/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
We discuss the relationship between constant-width branching programs and a hierarchy of languages lying between P and PSPACE. We introduce a notion of serializability. A computation is [Formula: see text]-serializable if it can be organized into a sequence of local computations, c 1 , c 2 ,…, c r , each of limited power (imposed by the complexity class [Formula: see text]), each passing only a few bits of information (a bottleneck) as the result of its computation to the next local computation. By an application of Barrington’s method on branching programs we show that PSPACE is LOGSPACE-serializable with a constant-width bottleneck.