Computing LOGCFL certi # cates
Computing LOGCFL certi # cates
复制标题
计算 LOGCFL 证书
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Francesco Scarcello
中科院分区：
文献类型：
--
作者：
G. Gottlob;N. Leone;Francesco Scarcello
复杂性类LOGCFL由可将对数空间简化为上下文无关语言的所有语言(或决策问题)组成。由于LOGCFL包含在AC中，因此LOGCFL中的问题具有高度的并行性。根据Ruzzo(JCSS21(1980)218)的结果，复杂性类LOGCFL可以刻画为使用对数空间且具有多项式大小的接受计算树的交替图灵机(ATM)所接受的语言类。我们证明，对于识别LOGCFL语言A的每一个这样的ATM M，都可以构造一个L换能器TM，使得输入w∈A上的TM输出一个关于w上M的接受树。由此得出，计算单个LOGCFL certi#Cates在函数式AC中是可行的，因此是高度并行化的。Wanke(J.算法16(1994)470)最近证明，对于任意的k，判定一个图的树宽是否至多为k是在复杂性类LOGCFL中。作为我们一般结果的一个应用，我们证明了计算常树宽图的树分解的任务是在泛函LOGCFL中的，因此在AC中也是如此。我们还证明了以下任务都是高度可并行化的：计算非循环约束满足问题的解；计算有界树宽的图的m-着色；计算有界树宽的图的色数和最小着色。C©2002 Elsevier Science B.V.保留所有权利。
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, 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 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 transducer TM such that TM on input w ∈ A outputs an accepting tree for M on w. It follows that computing single LOGCFL certi#cates is feasible in functional AC and is thus highly parallelizable. Wanke (J. Algorithms 16 (1994) 470) has recently shown that for any #xed 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. 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 treewidth. c © 2002 Elsevier Science B.V. All rights reserved.