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 条
  • [31] A framework for the integration of partial evaluation and abstract interpretation of logic programs
    Leuschel, M
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 2004, 26 (03): : 413 - 463
  • [32] FDNC: Decidable Nonmonotonic Disjunctive Logic Programs with Function Symbols
    Eiter, Thomas
    Simkus, Mantas
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2010, 11 (02)
  • [33] On parallel complexity of analytic functions
    Yu, Fuxiang
    Ko, Ker-I
    THEORETICAL COMPUTER SCIENCE, 2013, 489 : 48 - 57
  • [34] THE COMPLEXITY OF LOGIC-BASED ABDUCTION
    EITER, T
    GOTTLOB, G
    JOURNAL OF THE ACM, 1995, 42 (01) : 3 - 42
  • [35] The Complexity of Reasoning for Fragments of Autoepistemic Logic
    Creignou, Nadia
    Meier, Arne
    Vollmer, Heribert
    Thomas, Michael
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2012, 13 (02)
  • [36] Analysis of Recursively Parallel Programs
    Bouajjani, Ahmed
    Emmi, Michael
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 2013, 35 (03):
  • [37] Analysis of Recursively Parallel Programs
    Bouajjani, Ahmed
    Emmi, Michael
    ACM SIGPLAN NOTICES, 2012, 47 (01) : 203 - 214
  • [38] Backdoors to Normality for Disjunctive Logic Programs
    Fichte, Johannes K.
    Szeider, Stefan
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2015, 17 (01)
  • [39] Global analysis of constraint logic programs
    DeLaBanda, MG
    Hermenegildo, M
    Bruynooghe, M
    Dumortier, V
    Janssens, G
    Simoens, W
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1996, 18 (05): : 564 - 614
  • [40] SUSPENSION ANALYSES FOR CONCURRENT LOGIC PROGRAMS
    CODISH, M
    FALASLCHI, M
    MARRIOTT, K
    ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1994, 16 (03): : 649 - 686
12345