Games and total Datalog\(^{\lnot}\) queries (Q1575136)

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.