Discreet Games, Light Affine Logic and PTIME Computation

A. S. Murawski and C.-H. L. Ong

To appear at Computer Science Logic 2000 (CSL 2000), Fischbachau near Munich, Germany, 21-26 August 2000


Abstract

This paper introduces a model of IMLAL, the intuitionistic multiplicative fragment of Light Affine Logic, based on games and discreet strategies. We define a generalised notion of threads, so that a play of a game (of depth k) may be regarded as a number of interwoven threads (of depths ranging from 1 to k). To constrain the way threads communicate with each other, we organise them into networks at each depth (up to k), in accord with a protocol: * A network comprises an O-thread (which can only be created by O) and finitely many P-threads (which can only be created by P). * A network whose O-thread arises from a shriek-game can have at most one P-thread which must also arise from a shriek-game. * No thread can belong to more than one network. * Only O can switch between networks, and only P can switch between threads within the same network. Strategies that comply with the protocol are called discreet, and they give rise to a fully complete model of IMLAL. Since IMLAL has a polytime cut-elimination procedure, the model gives a basis for a denotational-semantic characterisation of PTIME.


Server START Conference Manager
Update Time 19 Apr 2000 at 10:13:07
Maintainer csl2000-org@tcs.informatik.uni-muenchen.de.
Start Conference Manager
Conference Systems