PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE

DOI10.1142/S0129054100000351zbMath0971.68043OpenAlexW2047754004MaRDI QIDQ4528765

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)

Related Items (3)

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 ⋮ Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic

Uses Software

• Datalog

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

This page was built for publication: PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE