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)

Full work available at URL https://doi.org/10.1007/BF01762108

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)

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

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)