Games and total Datalog^ queries
We show that the expressive power of Datalog\(^{\lnot}\) programs under the well-founded semantics does not decrease when restricted to total programs thereby affirmatively answering an open question posed by \textit{S. Abiteboul, R. Hill} and \textit{V. Vianu} [Foundations of databases (1995; Zbl 0848.68031)]. In particular, we show that for every such program there exists an equivalent total program whose only recursive rule is of the form \[ \text{win}(\bar{X}) \leftarrow\;\text{move}(\bar{X},\bar{Y}), \lnot \text{win}(\bar{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.
- Datalog extensions for database queries and updates
- Fundamental properties of deterministic and nondeterministic extensions of Datalog
- scientific article; zbMATH DE number 803291 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- scientific article; zbMATH DE number 850318 (Why is no real title available?)
- Relational queries computable in polynomial time
- The alternating fixpoint of logic programs with negation
This page was built for publication: Games and total Datalog\(^{\lnot}\) queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1575136)
