when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-16519

Galanaki, Chrysida ; Rondogiannis, Panos ; Wadge, William W.

General Logic Programs as Infinite Games

Dokument 1.pdf (209 KB)


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.

BibTeX - Entry

  author =	{Chrysida Galanaki and Panos Rondogiannis and William W. Wadge},
  title =	{General Logic Programs as Infinite Games},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  year =	{2008},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  number =	{08271},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Infinite Games, Negation in Logic Programming, Well-Founded Semantics}

Keywords: Infinite Games, Negation in Logic Programming, Well-Founded Semantics
Seminar: 08271 - Topological and Game-Theoretic Aspects of Infinite Computations
Issue date: 2008
Date of publication: 05.11.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI