General Logic Programs as Infinite Games

Abstract

In [vE86] M.H. van Emden introduced a simple game semantics for definite logic programs. Recently [RW05,GRW05], the authors extended this game to apply to logic programs with negation. Moreover, under the assumption that the programs have a finite number of rules, it was demonstrated in [RW05,GRW05] that the game is equivalent to the well-founded semantics of negation. In this paper we present work-in-progress towards demonstrating that the game of [RW05,GRW05] is equivalent to the well-founded semantics even in the case of programs that have a countably infinite number of rules. We argue however that in this case the proof of correctness has to be more involved. More specifically, in order to demonstrate that the game is correct one has to define a refined game in which each of the two players in his first move makes a bet in the form of a countable ordinal. Each ordinal can be considered as a kind of clock that imposes a "time limit" to the moves of the corresponding player. We argue that this refined game can be used to give the proof of correctness for the countably infinite case.