Games and total Datalog ¬ queries

Jörg Flum, Max Kubierschky, Bertram Ludäscher

Research output: Contribution to journalArticlepeer-review

Abstract

We show that the expressive power of Datalog ¬ programs under the well-founded semantics does not decrease when restricted to total programs thereby affirmatively answering an open question posed by Abiteboul et al. (Foundations of Databases, Addison-Wesley, Reading, MA, 1995). 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̄, Ȳ), ¬win(Ȳ), 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.

Original languageEnglish (US)
Pages (from-to)257-276
Number of pages20
JournalTheoretical Computer Science
Volume239
Issue number2
DOIs
StatePublished - May 28 2000
Externally publishedYes

Keywords

  • Datalog
  • Fixpoint logics
  • Games
  • Well-founded semantics

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Games and total Datalog ¬ queries'. Together they form a unique fingerprint.

Cite this