Parallel complexity of logical query programs
DOI10.1007/BF01762108zbMATH Open0646.68062MaRDI QIDQ1104095FDOQ1104095
Authors: Jeffrey D. Ullman, Allen Van Gelder 
Publication date: 1988
Published in: Algorithmica (Search for Journal in Brave)
Recommendations
context-free languagePRAM algorithm\({\mathcal N}{\mathcal C}\)chain programDatalog programsgeneralized sequential machinelogic programs without function symbolslogical query programsparallel time complexitypolynomial fringe
Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25)
Cites Work
- Title not available (Why is that?)
- A taxonomy of problems with fast parallel algorithms
- An observation on time-storage trade off
- The Semantics of Predicate Logic as a Programming Language
- Complete problems for deterministic polynomial time
- Fast Parallel Computation of Polynomials Using Few Processors
- Simulation of Parallel Random Access Machines by Circuits
- Finite-Turn Pushdown Automata
- The Hardest Context-Free Language
- Title not available (Why is that?)
- Contributions to the Theory of Logic Programming
- A note on undecidable properties of formal languages
- Tree-size bounded alternation
- Structure and complexity of relational queries
- Title not available (Why is that?)
- Alternation and the computational complexity of logic programs
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Modern Datalog Engines
- Inherent complexity of recursive queries
- Title not available (Why is that?)
- Rational index of languages defined by grammars with bounded dimension of parse trees
- Title not available (Why is that?)
- Ordered structures for parallel rule-based computations
- On the equivalence of recursive and nonrecursive Datalog programs
- Membership for growing context-sensitive grammars is polynomial
- Parallel bottom-up processing of datalog queries
- Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
- Bounds in the propagation of selection into logic programs
- 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 simple logic programs
- The parallel complexity of single rule logic programs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the parallel complexity of loops
- 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)
