On datalog vs polynomial time

DOI10.1006/JCSS.1995.1060MaRDI QIDQ1900923zbMATH OpenOpenAlexFDO

Authors Stavros S. Cosmandakis, Mihalis Yannakakis, Foto N. Afrati

Publication date 25 October 1995

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1995.1060

zbMATH Keywords

pumping lemmadatalog

Mathematics Subject Classification ID

Logic programming (68N17)

Recommendations

• On the expressive power of Datalog: tools and a case study.
• Datalog vs first-order logic
• Datalog extensions for database queries and updates
• Inherent complexity of recursive queries
• More on tractable disjunctive Datalog

Cited in

(17)

• On Datalog vs. LFP
• Computing with infinitary logic
• On transformations into linear database logic programs
• The expressiveness of DAC
• A datalog-based computational model for coordination-free, data-parallel systems
• Modern Datalog Engines
• Datalog vs first-order logic
• On the expressive power of Datalog: tools and a case study.
• Preservation theorems in finite model theory
• Mathematical Foundations of Computer Science 2005
• Inherent complexity of recursive queries
• On the complexity of single-rule datalog queries.
• The Complexity of Datalog on Linear Orders
• More on tractable disjunctive Datalog
• Is there a logic for polynomial time?
• Bounds in ontology-based data access via circuit complexity
• The expressive power of revised Datalog on problems with closure properties

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: On datalog vs polynomial time

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