Games and Total DatalogNeg Queries
Abstract.
We show that the expressive power of DatalogNeg programs under the
well-founded semantics does not decrease when restricted to total
programs thereby affirmatively answering an open question posed by
Abiteboul, Hull, and Vianu [AHV95]. In particular, we show that
for every such program there exists an equivalent total
program whose only recursive rule is of the form
- win(X) <- move(X, Y),
not win(Y)
where move is definable by a quantifier-free first-order
formula. Also for the noninflationary semantics we derive a new
normal form whose only recursive rule simulates a version of the
game of life.
[PS-File]