Undecidability and intractability results concerning datalog programs and their persistency numbers

DOI10.1145/1656242.1656247zbMath1351.68070OpenAlexW2072786848MaRDI QIDQ2946600

Eugénie Foustoucos, Anastasios Sidiropoulos, Stavros S. Cosmandakis

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

undecidabilityboundednessintractabilityDatalogbounded treewidth hypergraphspersistency numberspersistent variables

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Logic programming (68N17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Uses Software

• Datalog