Games and total Datalog\(^{\lnot}\) queries (Q1575136): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4864249 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fundamental properties of deterministic and nondeterministic extensions of Datalog / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Datalog extensions for database queries and updates / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4850061 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4866342 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Relational queries computable in polynomial time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The alternating fixpoint of logic programs with negation / rank | |||
Normal rank |
Revision as of 13:09, 30 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Games and total Datalog\(^{\lnot}\) queries |
scientific article |
Statements
Games and total Datalog\(^{\lnot}\) queries (English)
0 references
21 August 2000
0 references
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.
0 references
datalog
0 references
well-founded semantics
0 references
fixpoint logics
0 references
games
0 references