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 条
  • [1] ON THE COMPLEXITY OF DATA-FLOW ANALYSIS OF LOGIC PROGRAMS
    DEBRAY, SK
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1995, 17 (02): : 331 - 365
  • [2] Parallel Abductive Query Answering in Probabilistic Logic Programs
    Simari, Gerardo I.
    Dickerson, John P.
    Sliva, Amy
    Subrahmanian, V. S.
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2013, 14 (02)
  • [3] Molecular implementation of simple logic programs
    Ran, Tom
    Kaplan, Shai
    Shapiro, Ehud
    NATURE NANOTECHNOLOGY, 2009, 4 (10) : 642 - 648
  • [4] A Rendezvous of Logic, Complexity, and Algebra
    Chen, Hubie
    ACM COMPUTING SURVEYS, 2009, 42 (01)
  • [5] Complexity and expressive power of logic programming
    Dantsin, E
    Eiter, T
    Gottlob, G
    Voronkov, A
    ACM COMPUTING SURVEYS, 2001, 33 (03) : 374 - 425
  • [6] Logic Programs with Propositional Connectives and Aggregates
    Ferraris, Paolo
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2011, 12 (04) : 1 - 40
  • [7] Partial evaluation of functional logic programs
    Alpuente, M
    Falaschi, M
    Vidal, G
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1998, 20 (04): : 768 - 844
  • [8] Sharing and groundness dependencies in logic programs
    Codish, M
    Sondergaard, H
    Stuckey, PJ
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1999, 21 (05): : 948 - 976
  • [9] DENOTATIONAL ABSTRACT INTERPRETATION OF LOGIC PROGRAMS
    MARRIOTT, K
    SONDERGAARD, H
    JONES, ND
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1994, 16 (03): : 607 - 648
  • [10] On Characterizing the Data Access Complexity of Programs
    Elango, Venmugil
    Rastello, Fabrice
    Pouchet, Louis-Noel
    Ramanujam, J.
    Sadayappan, P.
    ACM SIGPLAN NOTICES, 2015, 50 (01) : 567 - 580
12345