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
相关论文
共 50 条
  • [21] EFFICIENT DATA-FLOW ANALYSIS OF LOGIC PROGRAMS
    DEBRAY, SK
    JOURNAL OF THE ACM, 1992, 39 (04) : 949 - 984
  • [22] Analyzing security protocols with secrecy types and logic programs
    Abadi, M
    Blanchet, B
    JOURNAL OF THE ACM, 2005, 52 (01) : 102 - 146
  • [23] Automated Termination Proofs for Logic Programs by Term Rewriting
    Schneider-Kamp, Peter
    Giesl, Juergen
    Serebrenik, Alexander
    Thiemann, Rene
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2009, 11 (01)
  • [24] An unfold/fold transformation framework for definite logic programs
    Roychoudhury, A
    Kumar, KN
    Ramakrishnan, CR
    Ramakrishnan, IV
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 2004, 26 (03): : 464 - 509
  • [25] A logic for information flow in object-oriented programs
    Amtoft, T
    Bandhakavi, S
    Banerjee, A
    ACM SIGPLAN NOTICES, 2006, 41 (01) : 91 - 102
  • [26] Nontermination inference of logic programs
    Payet, E
    Mesnard, F
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 2006, 28 (02): : 256 - 289
  • [27] Splitting Epistemic Logic Programs
    Cabalar, Pedro
    Fandinno, Jorge
    Del Cerro, Luis Farinas
    THEORY AND PRACTICE OF LOGIC PROGRAMMING, 2021, 21 (03) : 296 - 316
  • [28] The Complexity of Positive First-Order Logic without Equality
    Madelaine, Florent
    Martin, Barnaby
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2012, 13 (01)
  • [29] Expressiveness of Logic Programs under the General Stable Model Semantics
    Zhang, Heng
    Zhang, Yan
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2017, 18 (02)
  • [30] Controlling generalization and polyvariance in partial deduction of normal logic programs
    Leuschel, M
    Martens, B
    De Schreye, D
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1998, 20 (01): : 208 - 258
12345