G. Gottlob, N. Leone, F. Scarcello:

"Computing LOGCFL certificates";

Theoretical Computer Science,270(2002), 1-2; 761 - 777.

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 Ruzzo (JCSS 21 (1980)218), the complexity class LOGCFL can be characterized as the class of languages accepted by alternating Turing machines (ATMs) which use logarithmic space and have polynomally 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}on input wEuroA outputs an accepting tree for M on w. It follows that computing single LOGCFL certificates is feasible in functional AC#1{1} and is thus highly parallelizable.

Wanke (J. Algorithms 16 (1994)470) 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 follwing 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 treewidth.

Created from the Publication Database of the Vienna University of Technology.