Undecidable boundedness problems for datalog programs

DOI10.1016/0743-1066(95)00051-KMaRDI QIDQ3128622zbMATH OpenOpenAlexFDO

Authors Gerd G. Hillebrand, Paris C. Kanellakis, Moshe Y. Vardi, Harry G. Mairson

Publication date 17 April 1997

Published in The Journal of Logic Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0743-1066(95)00051-k

zbMATH Keywords

undecidabilityDatalog program

Mathematics Subject Classification ID

Logic programming (68N17)

Recommendations

• Boundedness is undecidable for datalog programs with a single recursive rule
• About Boundedness for some Datalog and Datalog^neg Programs
• Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs
• Undecidable optimization problems for database logic programs

Cited in

(28)

• The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs
• Undecidability and intractability results concerning Datalog programs and their persistency numbers
• Datalog programs and their persistency numbers
• Deciding the bisimilarity relation between Datalog goals
• Eliminating recursion from monadic datalog programs on trees
• scientific article; zbMATH DE number 219219 (Why is no real title available?)
• Bounded nondeterminism of logic programs
• Stack size analysis for interrupt-driven programs
• On the equivalence of recursive and nonrecursive Datalog programs
• Undecidable optimization problems for database logic programs
• On the decidability of the termination problem of active database systems
• On the k-Boundedness for Existential Rules
• Boundedness is undecidable for datalog programs with a single recursive rule
• Depth-bounded bottom-up evaluation of logic programs
• Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
• On the complexity of single-rule datalog queries.
• A simple characterization of uniform boundedness for a class of recursions
• About boundedness for some DATALOG and DATALOG\textsuperscript{neg} programs
• Restricted chase termination for existential rules: a hierarchical approach and experimentation
• Characterizing boundedness in chase variants
• A tetrachotomy of ontology-mediated queries with a covering axiom
• scientific article; zbMATH DE number 7471691 (Why is no real title available?)
• Modern Datalog: concepts, methods, applications (invited paper)
• Nonrecursive incremental evaluation of Datalog queries
• The unwind property for programs with bounded memory
• On Bounded Database Schemes and Bounded Horn-Clause Programs
• PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE
• A decompositional approach for computing least fixed-points of datalog programs with \(\mathcal Z\)-counters

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Undecidable boundedness problems for datalog programs

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