Constructing strategies in subclasses of McNaughton games.
Imran Khaliq, Gulshad Imran · Cologne Twente Workshop on Graphs and Combinatorial Optimization · 2013
We present algorithms for extracting winning strategies in subclasses of McNaughton games called update games and fully separated games. We also present an algorithm that solves update games with a bounded number of nondeterministic nodes in linear time which is an improvement over a quadratic time algorithm in update games.