THE PARALLEL COMPLEXITY OF SIMPLE LOGIC PROGRAMS

被引：11

作者：

AFRATI, F

PAPADIMITRIOU, CH

机构：

[1] STANFORD UNIV,STANFORD,CA 94305

[2] UNIV CALIF SAN DIEGO,DEPT COMP SCI,LA JOLLA,CA 92093

来源：

JOURNAL OF THE ACM | 1993年 / 40卷 / 04期

关键词：

ALA; LNA; THN; ALGORITHMS; LANGUAGES; THEORY; AUTOMATON; NC; P-COMPLETENESS; POLYNOMIAL FRINGE; POLYNOMIAL STOCK; PUSHDOWN;

D O I：

10.1145/153724.153752

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider logic programs with a single recursive rule, whose right-hand side consists of binary relations forming a chain. We give a complete characterization of all programs of this form that are computable in NC (assuming that P not-equal NC). Our proof uses ideas from automata and language theory, and the combinatories of strings.

引用

页码：891 / 916

页数：26

共 10 条

[1]

BABES E, 1989, THESIS NATIONAL TECH, P280

[2]

COSMADAKIS SC, 1986, 5TH P PRINC DAT SYST

[3]

GAIFMAN E, 1987, 1987 P S LOG COMP SC, P106

[4]

Hopcroft JE, 1979, INTRO AUTOMATA LANGU

[5] RELATIONAL QUERIES COMPUTABLE IN POLYNOMIAL-TIME [J].

IMMERMAN, N .

INFORMATION AND CONTROL, 1986, 68 (1-3) :86-104

[6]

KANELLAKIS PC, 1987, UNPUB

[7]

Lewis HR, 1982, ELEMENTS THEORY COMP

[8]

PAPADIMITRIOU CH, 1985, B EATCS

[9] PARALLEL COMPLEXITY OF LOGICAL QUERY PROGRAMS [J].

ULLMAN, JD ;

VANGELDER, A .

ALGORITHMICA, 1988, 3 (01) :5-42

[10]

VARDI MY, 1982, 14TH P ACM S THEOR C, P137

← 1 →