Parallel complexity of logical query programs

DOI10.1007/BF01762108MaRDI QIDQ1104095zbMATH OpenFDO

Authors Jeffrey D. Ullman, Allen Van Gelder

Publication date 1988

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

context-free languagePRAM algorithm\({\mathcal N}{\mathcal C}\)chain programDatalog programsgeneralized sequential machinelogic programs without function symbolslogical query programsparallel time complexitypolynomial fringe

Mathematics Subject Classification ID

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

Recommendations

• The parallel complexity of single rule logic programs
• The parallel complexity of simple logic programs
• scientific article; zbMATH DE number 4049157
• Parallel bottom-up processing of datalog queries
• Inherent complexity of recursive queries

Cites work

• scientific article; zbMATH DE number 4199654 (Why is no real title available?)
• scientific article; zbMATH DE number 3958731 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• A note on undecidable properties of formal languages
• A taxonomy of problems with fast parallel algorithms
• Alternation and the computational complexity of logic programs
• An observation on time-storage trade off
• Complete problems for deterministic polynomial time
• Contributions to the Theory of Logic Programming
• Fast Parallel Computation of Polynomials Using Few Processors
• Finite-Turn Pushdown Automata
• Simulation of Parallel Random Access Machines by Circuits
• Structure and complexity of relational queries
• The Hardest Context-Free Language
• The Semantics of Predicate Logic as a Programming Language
• Tree-size bounded alternation

Cited in

(30)

• scientific article; zbMATH DE number 1405452 (Why is no real title available?)
• On the equivalence of recursive and nonrecursive Datalog programs
• Bounds in the propagation of selection into logic programs
• The parallel complexity of simple logic programs
• The parallel complexity of single rule logic programs
• Distribution policies for Datalog
• Coalgebraic semantics for parallel derivation strategies in logic programming
• Distribution policies for Datalog
• scientific article; zbMATH DE number 7471669 (Why is no real title available?)
• Membership for growing context-sensitive grammars is polynomial
• Rational index of languages defined by grammars with bounded dimension of parse trees
• OLDTNF-based evaluation method for handling recursive queries in deductive databases
• On the parallel complexity of loops
• scientific article; zbMATH DE number 219218 (Why is no real title available?)
• A tetrachotomy of ontology-mediated queries with a covering axiom
• Ordered structures for parallel rule-based computations
• Logical query optimization by proof-tree transformation
• Why a single parallelization strategy is not enough in knowledge bases
• A closed-form evaluation for Datalog queries with integer (gap)-order constraints
• scientific article; zbMATH DE number 176523 (Why is no real title available?)
• scientific article; zbMATH DE number 4049157 (Why is no real title available?)
• Modern Datalog Engines
• On the monotonicity of (LDL) logic programs with set.
• Inherent complexity of recursive queries
• On the complexity of single-rule datalog queries.
• Parallel bottom-up processing of datalog queries
• Logic Programming
• scientific article; zbMATH DE number 176243 (Why is no real title available?)
• Exploiting parallelism in coalgebraic logic programming
• Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic

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)