The UvA-LINKER will give you a range of other options to find the full text of a publication (including a direct link to the full-text if it is located on another database on the internet).
De UvA-LINKER biedt mogelijkheden om een publicatie elders te vinden (inclusief een directe link naar de publicatie online als deze beschikbaar is in een database op het internet).


Zoekopdracht: faculteit: "FNWI" en publicatiejaar: "2010"

AuteurP. van Emde Boas
TitelPlaying Savitch and Cooking games
Boek/bron titelConcurrency, compositionality, and correctness: essays in honor of Willem-Paul de Roever
Auteurs/EditorsD. Dams, U. Hannemann, M. Steffen
FaculteitFaculteit der Natuurwetenschappen, Wiskunde en Informatica
Instituut/afd.FNWI: Institute for Logic, Language and Computation (ILLC)
SamenvattingThe complexity class PSPACE is one of the most robust concepts in contemporary computer science. Aside from the fact that space is invariant (for reasonable models at least) up to a constant factor, the class can be characterized in many alternative ways, involving parallel computation, logic problems like QBF, interactive computation models but also by means of games.
In the literature the connection between PSPACE and games is established as a consequence either of the PSPACE completeness of the QBF problem or as a consequence of the properties of the alternating computation model. Based on either of these starts one subsequently has investigated the PSPACE completeness of endgame analysis problems for various specific games.
The purpose of this note is to present a direct reduction of an arbitrary PSPACE problem into endgame analysis of a corresponding game. As a consequence we obtain an alternative proof of the 1970 Savitch theorem showing that PSPACE is closed under nondeterminism. Furthermore we reconsider the direct translation of endgame analysis of some game in QBF, in order to obtain a better understanding of the conditions on the game which enable this translation.
Soort documentHoofdstuk
Document finderUvA-Linker