The parallel complexity of simple logic programs
Authors:
Open Access
- 1 September 1993
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 40 (4) , 891-916
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.Keywords
This publication has 3 references indexed in Scilit: