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 条
  • [41] Incremental analysis of constraint logic programs
    Hermenegildo, M
    Puebla, G
    Marriott, K
    Stuckey, PJ
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 2000, 22 (02): : 187 - 223
  • [42] SUSPENSION ANALYSES FOR CONCURRENT LOGIC PROGRAMS
    CODISH, M
    FALASLCHI, M
    MARRIOTT, K
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1994, 16 (03): : 649 - 686
  • [43] COST-ANALYSIS OF LOGIC PROGRAMS
    DEBRAY, SK
    LIN, NW
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1993, 15 (05): : 826 - 875
  • [44] On Local StratifiabUity of Logic Programs and Databases
    沈一栋
    童(兆页)
    程代杰
    Journal of Computer Science and Technology, 1993, (02) : 99 - 107
  • [45] Automatic inversion generates divide-and-conquer parallel programs
    Morita, Kazutaka
    Morihata, Akimasa
    Matsuzaki, Kiminori
    Hu, Zhenjiang
    Takeichi, Masato
    ACM SIGPLAN NOTICES, 2007, 42 (06) : 146 - 155
  • [46] Parallelism for free: Efficient and optimal bitvector analyses for parallel programs
    Knoop, J
    Steffen, B
    Vollmer, J
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1996, 18 (03): : 268 - 299
  • [47] Well-Founded Semantics for Description Logic Programs in the Semantic Web
    Eiter, Thomas
    Ianni, Giovambattista
    Lukasiewicz, Thomas
    Schindlauer, Roman
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2011, 12 (02)
  • [48] Inferring non-suspension conditions for logic programs with dynamic scheduling
    Genaim, Samir
    King, Andy
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2008, 9 (03)
  • [49] From Functional Logic Programs to Purely Functional Programs Preserving Laziness
    Brassel, Bernd
    Fischer, Sebastian
    IMPLEMENTATION AND APPLICATION OF FUNCTIONAL LANGUAGES, 2011, 5836 : 25 - 42
  • [50] Probabilistic logic under coherence: complexity and algorithms
    Veronica Biazzo
    Angelo Gilio
    Thomas Lukasiewicz
    Giuseppe Sanfilippo
    Annals of Mathematics and Artificial Intelligence, 2005, 45 : 35 - 81
12345