Parallel complexity of logical query programs (Q1104095)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parallel complexity of logical query programs |
scientific article |
Statements
Parallel complexity of logical query programs (English)
0 references
1988
0 references
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 in \({\mathcal N}{\mathcal C}\). 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 in \({\mathcal N}{\mathcal C}\). Finally, we describe an approach for demonstrating that certain logical query programs are log space complete for \({\mathcal P}\), and apply it to both elementary single rule programs and nonelementary programs.
0 references
chain program
0 references
context-free language
0 references
generalized sequential machine
0 references
parallel time complexity
0 references
logic programs without function symbols
0 references
logical query programs
0 references
Datalog programs
0 references
PRAM algorithm
0 references
polynomial fringe
0 references
\({\mathcal N}{\mathcal C}\)
0 references