TY - GEN
T1 - How good is a strategy in a game with nature?
AU - Carayol, Arnaud
AU - Serre, Olivier
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/7/31
Y1 - 2015/7/31
N2 - We consider games with two antagonistic players - Éloïse (modelling a program) and Abelard (modelling a byzantine environment) - and a third, unpredictable and uncontrollable player, that we call Nature. Motivated by the fact that the usual probabilistic semantics very quickly leads to undecidability when considering either infinite game graphs or imperfect information, we propose two alternative semantics that leads to decidability where the probabilistic one fails: one based on counting and one based on topology.
AB - We consider games with two antagonistic players - Éloïse (modelling a program) and Abelard (modelling a byzantine environment) - and a third, unpredictable and uncontrollable player, that we call Nature. Motivated by the fact that the usual probabilistic semantics very quickly leads to undecidability when considering either infinite game graphs or imperfect information, we propose two alternative semantics that leads to decidability where the probabilistic one fails: one based on counting and one based on topology.
KW - Cardinality constraints
KW - Large sets of branches
KW - Qualitative study of games
KW - Tree automata
U2 - 10.1109/LICS.2015.62
DO - 10.1109/LICS.2015.62
M3 - Conference contribution
AN - SCOPUS:84945976232
T3 - Proceedings - Symposium on Logic in Computer Science
SP - 609
EP - 620
BT - Proceedings - 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015
Y2 - 6 July 2015 through 10 July 2015
ER -