Galanaki, Chrysida ;
Rondogiannis, Panos ;
Wadge, William W.
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 wellfounded semantics of negation. In this paper we present workinprogress towards demonstrating that the game of [RW05,GRW05] is equivalent to the wellfounded 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
@InProceedings{galanaki_et_al:DSP:2008:1651,
author = {Chrysida Galanaki and Panos Rondogiannis and William W. Wadge},
title = {General Logic Programs as Infinite Games},
booktitle = {Topological and GameTheoretic 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 = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1651},
annote = {Keywords: Infinite Games, Negation in Logic Programming, WellFounded Semantics}
}
Keywords: 

Infinite Games, Negation in Logic Programming, WellFounded Semantics 
Seminar: 

08271  Topological and GameTheoretic Aspects of Infinite Computations

Issue date: 

2008 
Date of publication: 

05.11.2008 