Parallel complexity of logical query programs |
| |
Authors: | Jeffrey D. Ullman and Allen Van Gelder |
| |
Affiliation: | (1) Department of Computer Science, Stanford University, 94305 Stanford, CA, USA;(2) Present address: Department of Computer Science, University of California, 95064 Santa Cruz, CA, USA |
| |
Abstract: | We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the polynomial fringe property, this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the linear and piecewise linear classes of logic programs are inNC. Then we examine several nonlinear classes in which the program has a single recursive rule that is an elementary chain. We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the polynomial fringe property; hence such programs are inNC Finally, we describe an approach for demonstrating that certain logical query programs are log space complete forP, and apply it to both elementary single rule programs and nonelementary programs.Supported by NSF Grant IST-84-12791, a grant of IBM Corporation, and ONR contract N00014-85-C-0731. |
| |
Keywords: | Chain program Complexity Context-free language Datalog Generalized sequential machine Logic program NC Parallelism Polynomial fringe PRAM |
本文献已被 SpringerLink 等数据库收录! |
|