PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE

DOI10.1142/S0129054100000351MaRDI QIDQ4528765zbMATH OpenOpenAlexFDO

Authors Ron van der Meyden

Publication date 11 February 2001

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054100000351

zbMATH Keywords

datalog programs

Mathematics Subject Classification ID

Database theory (68P15)

Recommendations

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

Cites work

• Data independent recursion in deductive databases
• Relationships between nondeterministic and deterministic tape complexities
• The theory of well-quasi-ordering: a frequently discovered concept

Cited in

(7)

• Boundedness is undecidable for datalog programs with a single recursive rule
• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• A tetrachotomy of ontology-mediated queries with a covering axiom
• scientific article; zbMATH DE number 219219 (Why is no real title available?)
• About boundedness for some DATALOG and DATALOG\textsuperscript{neg} programs
• Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
• 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: PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE

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