Open AccessA Lattice Theory for Solving Games of Imperfect Information
Author(s) -
Martin Wulf,
Laurent Doyen,
Jean-François Raskin
Publication year - 2006
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-33170-0
DOI - 10.1007/11730637_14
Subject(s) - decidability , automaton , imperfect , computer science , perfect information , lattice (music) , point (geometry) , automata theory , fixed point , fixed point theorem , theoretical computer science , discrete mathematics , mathematical economics , mathematics , linguistics , mathematical analysis , philosophy , physics , geometry , acoustics
In this paper, we propose a fixed point theory to solve games of imperfect information. The fixed point theory is defined on the lattice of antichains of sets of states. Contrary to the classical solution proposed by Reif [Rei84], our new solution does not involve determinization. As a consequence, it is readily applicable to classes of systems that do not admit determinization. Notable examples of such systems are timed and hybrid automata. As an application, we show that the discrete control problem for games of imperfect information defined by rectangular automata is decidable. This result extends a result by Henzinger and Kopke in [HK99].
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom