UT professor Mariëlle Stoelinga has been awarded the Test of Time Award at the International Conference on Concurrency Theory (CONCUR), a highly regarded worldwide scientific meeting in the field of theoretical computing. The award is given for historical scientific publications that still have relevance in their field today.
In 2003, Mariëlle, who is a professor in Risk Management for High-tech systems, wrote the paper The The Element of Surprise in Timed Games, together with colleagues from UC Santa Cruz, UC Berkeley (both USA) and the Università di Salerno (Italy). In the paper, the researchers consider concurrent two-person games played in real-time, in which the players decide both which action to play, and when to play it. Such timed games differ from untimed games in two essential ways. First, players can take each other by surprise, because actions are played with delays that cannot be anticipated by the opponent. Second, a player should not be able to win the game by preventing time from diverging. They present a model of timed games that preserves the element of surprise and accounts for time divergence in a way that treats both players symmetrically and applies to all ω-regular winning conditions.
"We prove that the ability to take each other by surprise adds extra power to the players", Mariëlle says. "For the case that the games are specified in the style of timed automata, they provide symbolic algorithms for their solution with respect to all ω-regular winning conditions. They also show that for these timed games, memory strategies are more powerful than memoryless strategies already in the case of reachability objectives."
Why is the paper so impactful? Mariëlle: "Many other scientists have investigated our games-with-time further. For example, with more players and more complicated conditions. In addition, these games form the theoretical basis for calculating winning strategies for all kinds of practical problems, e.g. algorithms to control robots. The robot is then player one, and the environment is player two. A winning strategy in our game then corresponds to a strategy for the robot to achieve (in a random environment) a certain goal, e.g. to clean up all the cans lying around on a lawn."