ScholarLens Back to search
2000•International Journal of Foundations of Computer ScienceRequires access

PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE

Ron van der Meyden

Open publisher page 11 citations

Abstract

Datalog programs, are a special case of logic programs without function symbols. Detection of boundedness permits Datalog programs to be optimized by the elimination of recursion. To determine whether a predicate is bounded in a Datalog program is known to be undecidable. However, previous work (Cosmadakis et al., 20th ACM Symposium on the Theory of Computing, 1988) has show that for monadic Datalog, this problem is decidable, with upper and lower bounds of EXPSPACE and PSPACE respectively for linear monadic programs. We establish that predicate boundedness for linear monadic programs is in fact in PSPACE, yielding a tight bound for this problem.a

About this research paper

What this paper is about

Datalog programs, are a special case of logic programs without function symbols. Detection of boundedness permits Datalog programs to be optimized by the elimination of recursion. To determine whether a predicate is bounded in a Datalog program is known to be undecidable. However, previous work (Cosmadakis et al., 20th ACM Symposium on the Theory of Computing, 1988) has show that for monadic Datalog, this problem is decidable, with upper and lower bounds of EXPSPACE and PSPACE respectively for linear monadic programs. We establish that predicate boundedness for linear monadic programs is in fact in PSPACE, yielding a tight bound for this problem.a

Why it matters

OpenAlex reports 11 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Datalog programs, are a special case of logic programs without function symbols. Detection of boundedness permits Datalog programs to be optimized by the elimination of recursion. To determine whether a predicate is bounded in a Datalog program is known to be undecidable. However, previous work (Cosmadakis et al., 20th ACM Symposium on the Theory of Computing, 1988) has show that for monadic Datalog, this problem is decidable, with upper and lower bounds of EXPSPACE and PSPACE respectively for linear monadic programs. We establish that predicate boundedness for linear monadic programs is in fact in PSPACE, yielding a tight bound for this problem.a

Key concepts: Datalog, Undecidable problem, Decidability, Predicate (mathematical logic), PSPACE, Monadic predicate calculus, Mathematics, Recursion (computer science)

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE — Research Paper | ScholarLens