Parallel Complexity of Logical Query Programs,
Abstract
This document considers the parallel time complexity of logic programs without function symbols, called logical query programs. The authors 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 logarithmic time. As a result, the linear and piecewise linear classes of logic programs are in NC. Then they examine several nonlinear cases in which the program has a single recursive rule that is an elementary chain. Among such elementary single rule programs that are nonlinear, some can easily be shown to have an equivalent linear program, hence are in NC. It is shown 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 in NC. Finally, the authors describe an approach for demonstrating that certain logical query programs are log space complete for P, and apply it to both elementary single rule programs and nonelementary programs. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 20, 1985
- Accession Number
- ADA167441
Entities
People
- Allen Van Gelder
- Jeffrey D. Ullman
Organizations
- Stanford University