The parallel complexity of simple logic programs

DOI10.1145/153724.153752MaRDI QIDQ4271089zbMATH OpenOpenAlexFDO

Authors Foto N. Afrati, Christos Papadimitriou

Publication date 1993

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/153724.153752

zbMATH Keywords

NCpushdownpolynomial fringe\(P\)-completenesspolynomial stock

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic programming (68N17)

Recommendations

• The parallel complexity of single rule logic programs
• Parallel complexity of logical query programs
• scientific article; zbMATH DE number 4049157
• scientific article; zbMATH DE number 4199606
• scientific article; zbMATH DE number 176199

Cited in

(10)

• Inherent complexity of recursive queries
• scientific article; zbMATH DE number 4049157 (Why is no real title available?)
• A Characterization of NC k by First Order Functional Programs
• Parallel complexity of logical query programs
• Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
• Modular materialisation of Datalog programs
• On the complexity of single-rule datalog queries.
• A tetrachotomy of ontology-mediated queries with a covering axiom
• Linearisability on Datalog programs
• The parallel complexity of single rule logic programs

This page was built for publication: The parallel complexity of simple logic programs

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