Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twelfth Annual IEEE Symposium on

Logic in Computer Science (LICS 1997)

Paper: How much memory is needed to win infinite games? (at LICS 1997)

Authors: Stefan Dziembowski Marcin Jurdzinski Igor Walukiewicz

Abstract

We consider a class of infinite two-player games on finitely coloured graphs. Our main question is: given a winning condition, what is the inherent blow-up (additional memory) of the size of the I/O automata realizing winning strategies in games with this condition. This problem is relevant to synthesis of reactive programs and to the theory of automata on infinite objects. We provide matching upper and lower bounds for the size of memory needed by winning strategies in games with a fixed winning condition. We also show that in the general case the LAR (latest appearance record) data structure of Gurevich and Harrington is optimal. Then we propose a more succinct way of representing winning strategies by means of parallel compositions of transition systems. We study the question: which classes of winning conditions admit only polynomial-size blowup of strategies in this representation.

BibTeX

  @InProceedings{DziembowskiJurdzins-Howmuchmemoryisneed,
    author = 	 {Stefan Dziembowski and Marcin Jurdzinski and Igor Walukiewicz},
    title = 	 {How much memory is needed to win infinite games?},
    booktitle =  {Proceedings of the Twelfth Annual IEEE Symposium on Logic in Computer Science (LICS 1997)},
    year =	 {1997},
    month =	 {June}, 
    pages =      {99--110},
    location =   {Warsaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski