The Parallel Complexity of Simple Logic Programs

Foto N. Afrati, Christos H. PapadimitriouJ. ACM 1993 · OpenReview

Abstract

We consider logic programs with a single recursive rules, 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 ≠ NC). Our proof uses ideas from automata and language theory, and the combinatorics of strings.
BibTeX
@article{afrati1993parallel,
  author = {Foto N. Afrati and Christos H. Papadimitriou},
  title = {{The Parallel Complexity of Simple Logic Programs}},
  journal = {J. ACM},
  year = {1993},
  url = {https://openreview.net/forum?id=N14VBQ-sQ7},
}

Loading related content...

Figure