THE PARALLEL COMPLEXITY OF SIMPLE LOGIC PROGRAMS

Authors
AFRATI F PAPADIMITRIOU CH
Citation
F. Afrati et Ch. Papadimitriou, THE PARALLEL COMPLEXITY OF SIMPLE LOGIC PROGRAMS, Journal of the Association for Computing Machinery, 40(4), 1993, pp. 891-916
Citations number
10
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics
Journal title
Journal of the Association for Computing Machinery
ISSN journal
00045411 → ACNP
Volume
40
Issue
4
Year of publication
1993
Pages
891 - 916
Database
ISI
SICI code
Abstract
We consider logic programs with a single recursive rule, whose right-h and side consists of binary relations forming a chain. We give a compl ete characterization of all programs of this form that are computable in NC (assuming that P not-equal NC). Our proof uses ideas from automa ta and language theory, and the combinatories of strings.