The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs

DOI10.1007/3-540-60922-9_35MaRDI QIDQ4593950zbMATH OpenOpenAlexFDO

Authors Jerzy Marcinkowski

Publication date 16 November 2017

Published in STACS 96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60922-9_35

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Undecidability and degrees of sets of sentences (03D35) Logic programming (68N17)

Recommendations

• Boundedness is undecidable for datalog programs with a single recursive rule
• Undecidable boundedness problems for datalog programs
• Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs
• scientific article; zbMATH DE number 219219
• Undecidability and intractability results concerning Datalog programs and their persistency numbers
• Trichotomy Results on the Complexity of Reasoning with Disjunctive Logic Programs
• The undecidability of FO3 and the calculus of relations with just one binary relation
• Tight, consistent, and computable completions for unrestricted logic programs
• About boundedness for some DATALOG and DATALOG\textsuperscript{neg} programs
• About Boundedness for some Datalog and Datalog^neg Programs

Cited in

(5)

• Boundedness is undecidable for datalog programs with a single recursive rule
• Unifications, deunifications, and their complexity
• On the complexity of single-rule datalog queries.
• Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs
• A semantic approach to optimize linear datalog programs

This page was built for publication: The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs

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