Advanced compilation techniques that target parallel computing architectures make heavy use of various abstractions of programming constructs to decide, at compile time, whether or not a piece of code can be executed in parallel with another. These choices depend on the data access patterns of the corresponding program statements; among other approaches, such decisions can be seen as checking the satisfiability of affine rational linear equations or inequalities.

Solving such systems is thus of key importance, particularly when they are extended to an algebra that includes min and max operators, enabling more precise program analyses. The introduction of min/max operators also makes this framework fit to represent stochastic games in which one player behaves as an outcome maximizer while the other strives to minimize it. Building on this metaphor, the authors propose extending the typical linear-programming-based techniques to solve such systems with two new game-like strategy improvement algorithms. One of the main advantages of this approach, and a key practical contribution of the paper, is that it can be used to perform a quite precise static analysis of programs based on the template polyhedral domain, a powerful data and program abstraction mechanism.

Even though the above summary might suggest a terse and dry paper, I enjoyed reading it. The writing is clear, and multiple examples lighten the reading, which is necessary in a paper of this length. The formalism is elegant and the applications are promising. Researchers with game theory or abstract interpretation concerns should find the reading effort quite rewarding.