Imperial College London
Alternate

Dr. Sebastian Uchitel

Faculty of Engineering, Department of Computing

Reader in Software Engineering
 
 
 
//

Contact

 

+44 (0)20 7594 8269s.uchitel Website

 
 
//

Location

 

573Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@inproceedings{Rodriguez:2016:10.1109/CDC.2016.7799347,
author = {Rodriguez, N and Braberman, V and D'Ippolito, N and Uchitel, S},
doi = {10.1109/CDC.2016.7799347},
pages = {6996--7001},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
title = {21/2-player generalized reactivity (1) games},
url = {http://dx.doi.org/10.1109/CDC.2016.7799347},
year = {2016}
}
Download

RIS format (EndNote, RefMan)

TY  - CPAPER
AB  - We introduce a new class of 21/2-player games, the 21/2-player GR(1) games, that allows for solving problems of stochastic nature by adding a probabilistic component to simple 2-player GR(1) games. Further, we present an efficient approach for solving qualitative 21/2-player GR(1) games with polynomial-time complexity. Our approach is based on a reduction from 21/2-player GR(1) games to 2-player GR(1) games that allows for solving the game and constructing, from a sure winning strategy for player  (resp. L) in a 2-player GR(1) game, an almost-sure (resp. positively) winning strategy for its corresponding 21/2-player GR(1) game. Key to the effectiveness of the proposed approach is the fact that the reduction generates a 2-player game that is linearly larger than the original 21/2-player game, more precisely, it is linear with respect to the number of probabilistic states in the 21/2-player GR(1) game.
AU  - Rodriguez,N
AU  - Braberman,V
AU  - D'Ippolito,N
AU  - Uchitel,S
DO  - 10.1109/CDC.2016.7799347
EP  - 7001
PB  - Institute of Electrical and Electronics Engineers (IEEE)
PY  - 2016///
SP  - 6996
TI  - 21/2-player generalized reactivity (1) games
UR  - http://dx.doi.org/10.1109/CDC.2016.7799347
UR  - http://hdl.handle.net/10044/1/44793
ER  -
Download