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

Datalog programundecidability

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

(33)

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

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)