Parallel complexity of logical query programs

DOI10.1007/BF01762108zbMath0646.68062MaRDI QIDQ1104095

Allen van Gelder, Jeffrey D. Ullman

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

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

Related Items

Exploiting parallelism in coalgebraic logic programming ⋮ On the monotonicity of (LDL) logic programs with set. ⋮ A tetrachotomy of ontology-mediated queries with a covering axiom ⋮ Distribution Policies for Datalog. ⋮ On the parallel complexity of loops ⋮ Modern Datalog Engines ⋮ On the complexity of single-rule datalog queries. ⋮ Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic ⋮ On the equivalence of recursive and nonrecursive Datalog programs ⋮ Why a single parallelization strategy is not enough in knowledge bases ⋮ Logical query optimization by proof-tree transformation ⋮ A closed-form evaluation for Datalog queries with integer (gap)-order constraints ⋮ Inherent complexity of recursive queries ⋮ Membership for growing context-sensitive grammars is polynomial ⋮ Coalgebraic Semantics for Parallel Derivation Strategies in Logic Programming ⋮ Bounds in the propagation of selection into logic programs ⋮ OLDTNF-based evaluation method for handling recursive queries in deductive databases ⋮ Distribution policies for Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tree-size bounded alternation
• An observation on time-storage trade off
• Complete problems for deterministic polynomial time
• Structure and complexity of relational queries
• Fast Parallel Computation of Polynomials Using Few Processors
• Simulation of Parallel Random Access Machines by Circuits
• A taxonomy of problems with fast parallel algorithms
• Alternation and the computational complexity of logic programs
• Contributions to the Theory of Logic Programming
• The Semantics of Predicate Logic as a Programming Language
• The Hardest Context-Free Language
• Finite-Turn Pushdown Automata
• A note on undecidable properties of formal languages