Computing LOGCFL certificates (Q5958329)

The complexity class LOGCFL consists of all languages (or decision problems) which are logspace reducible to a context-free language. Since LOGCFL is included in \(AC^{1}\), the problems in LOGCFL are highly parallelizable. By results of \textit{W. L. Ruzzo} [J. Comput. Syst. Sci. 21, 218-235 (1980; Zbl 0445.68034)], the complexity class LOGCFL can be characterized as the class of languages accepted by alternating Turing machines (ATMs) which use logarithmic space and have polynomially sized accepting computation trees. We show that for each such ATM \(M\) recognizing a language \(A\) in LOGCFL, it is possible to construct an \(L^{LOGCFL}\) transducer \(T_{M}\) such that \(T_{M}\) on input \(w \in A\) outputs an accepting tree for \(M\) on \(w.\) It follows that computing single LOGCFL certificates is feasible in functional \(AC^{1}\) and is thus highly parallelizable. \textit{E. Wanke} [J. Algorithms 16, No. 3, 470-491 (1994; Zbl 0804.68048)] has recently shown that for any fixed \(k,\) deciding whether the treewidth of a graph is at most \(k\) is in the complexity-class LOGCFL. As an application of our general result, we show that the task of computing a tree-decomposition for a graph of constant treewidth is in functional LOGCFL, and thus in \(AC^{1}.\) We also show that the following tasks are all highly parallelizable: Computing a solution to an acyclic constraint satisfaction problem; computing an \(m\)-coloring for a graph of bounded treewidth; computing the chromatic number and minimal colorings for graphs of bounded tree- width.