Parallel complexity of logical query programs

\({\mathcal N}{\mathcal C}\)chain program context-free language Datalog programs generalized sequential machine logic programs without function symbols logical query programs parallel time complexity polynomial fringe PRAM algorithm

Mathematics Subject Classification ID

Theory of operating systems (68N25) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

Cites work

Cited in

(30)

This page was built for publication: Parallel complexity of logical query programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104095)