TY - GEN
T1 - Extracting winning strategies in update games
AU - Khaliq, Imran
AU - Khoussainov, Bakhadyr
AU - Liu, Jiamou
PY - 2011/9/26
Y1 - 2011/9/26
N2 - This paper investigates algorithms for extracting winning strategies in two-player games played on finite graphs. We focus on a special class of games called update games. We present a procedure for extracting winning strategies in update games by constructing strategies explicitly. This is based on an algorithm that solves update games in quadratic time. We also show that solving update games with a bounded number of nonkdeterministic nodes takes linear time.
AB - This paper investigates algorithms for extracting winning strategies in two-player games played on finite graphs. We focus on a special class of games called update games. We present a procedure for extracting winning strategies in update games by constructing strategies explicitly. This is based on an algorithm that solves update games in quadratic time. We also show that solving update games with a bounded number of nonkdeterministic nodes takes linear time.
UR - http://www.scopus.com/inward/record.url?scp=80053042395&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-21875-0_15
DO - 10.1007/978-3-642-21875-0_15
M3 - Conference contribution
AN - SCOPUS:80053042395
SN - 9783642218743
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 142
EP - 151
BT - Models of Computation in Context - 7th Conference on Computability in Europe, CiE 2011, Proceedings
T2 - 7th Conference on Computability in Europe, CiE 2011
Y2 - 27 June 2011 through 2 July 2011
ER -