Energy mean-payoff games

Jean-Fran\c{c}ois Raskin; Mickael Randour; Quentin Hautem; V\'eronique Bruy\`ere

arxiv: 1907.01359 · v1 · pith:MVE6GE6Nnew · submitted 2019-07-02 · 💻 cs.GT

Energy mean-payoff games

V\'eronique Bruy\`ere , Quentin Hautem , Mickael Randour , Jean-Fran\c{c}ois Raskin This is my paper

Pith reviewed 2026-05-25 10:36 UTC · model grok-4.3

classification 💻 cs.GT

keywords energy gamesmean-payoff gamesinfinite memory strategiesgraph gamestwo-player gamesstrategy complexity

0 comments

The pith

In energy mean-payoff games the protagonist may need infinite memory while the antagonist needs none.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies infinite-duration games on finite graphs whose edges carry two-dimensional integer weights. The protagonist must satisfy an energy condition along the first coordinate and a mean-payoff condition along the second. It proves that the protagonist can require infinite memory to play optimally, yet the antagonist can always play optimally with memoryless strategies. The one-player decision problem lies in polynomial time; the two-player version lies in co-NP, and explicit constructions are given for the protagonist’s infinite-memory strategies.

Core claim

Optimal strategies for the protagonist in energy mean-payoff games may require infinite memory while optimal strategies for the antagonist require no memory. The one-player problem is solvable in polynomial time and the two-player problem belongs to co-NP, with effective constructions supplied for the infinite-memory strategies of the protagonist.

What carries the argument

Finite directed graphs with edges labeled by two-dimensional integer weight vectors, together with the standard energy objective on the first coordinate and mean-payoff objective on the second.

If this is right

The one-player energy mean-payoff decision problem can be solved in polynomial time.
The two-player energy mean-payoff decision problem lies in co-NP.
The antagonist always possesses an optimal memoryless strategy.
Effective, though infinite-memory, constructions exist for optimal protagonist strategies.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The memory distinction may recur in other multi-dimensional quantitative games on graphs.
Algorithmic tools for solving such games must accommodate infinite-memory representations for one player.
The co-NP membership may be tightened or shown tight by further complexity analysis of the two-player case.

Load-bearing premise

The underlying model consists of finite directed graphs equipped with integer two-dimensional weight vectors on edges, with energy and mean-payoff objectives defined in the usual way for such graphs.

What would settle it

A concrete finite graph with two-dimensional integer weights on which either the one-player decision problem requires super-polynomial time or an optimal antagonist strategy requires memory.

read the original abstract

In this paper, we study one-player and two-player energy mean-payoff games. Energy mean-payoff games are games of infinite duration played on a finite graph with edges labeled by 2-dimensional weight vectors. The objective of the first player (the protagonist) is to satisfy an energy objective on the first dimension and a mean-payoff objective on the second dimension. We show that optimal strategies for the first player may require infinite memory while optimal strategies for the second player (the antagonist) do not require memory. In the one-player case (where only the first player has choices), the problem of deciding who is the winner can be solved in polynomial time while for the two-player case we show co-NP membership and we give effective constructions for the infinite-memory optimal strategies of the protagonist.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper establishes that the protagonist needs infinite memory for optimal strategies in energy mean-payoff games while the antagonist needs none, with one-player in P and two-player in co-NP plus explicit constructions.

read the letter

The main point is that in these two-dimensional games on finite graphs, the first player may require infinite memory to win while the second player can always use memoryless strategies. The one-player problem is in P and the two-player version is in co-NP, with constructions given for the infinite-memory cases. This is the concrete output from pairing an energy objective on the first weight dimension with mean-payoff on the second. The setup uses standard integer vector labels and the usual definitions for both objectives, so the memory split and complexity bounds follow from combining existing techniques rather than inventing new machinery. The constructions make the infinite-memory claim usable rather than purely existential. The one-player polynomial-time result is unsurprising once the protagonist controls all moves and can track energy levels directly. The co-NP upper bound for two players aligns with the antagonist having positional strategies. No circularity or hidden parameters appear in the stated claims. The only real limitation is that the abstract leaves the detailed reductions and strategy constructions out of view, so full verification requires the proofs. That said, the overall picture is internally consistent and matches what the graph-games literature would predict for this objective pair. This work is aimed at people who already work on multi-objective graph games or verification problems that mix safety-style constraints with long-run averages. It is specific enough and the memory distinction is sharp enough that it deserves a serious referee to check the constructions and see whether the co-NP bound can be tightened.

Referee Report

0 major / 2 minor

Summary. The paper studies one- and two-player energy mean-payoff games on finite directed graphs whose edges are labeled by 2-dimensional integer weight vectors. The protagonist must satisfy an energy objective on the first coordinate and a mean-payoff objective on the second; the antagonist opposes. The central claims are that optimal protagonist strategies may require infinite memory while antagonist strategies are memoryless, that the one-player decision problem lies in P, that the two-player decision problem lies in co-NP, and that explicit constructions exist for the protagonist's infinite-memory strategies.

Significance. If the stated memory and complexity results hold, the work supplies a clean separation between the memory needs of the two players in a natural multi-objective setting and supplies both a polynomial-time algorithm for the one-player case and a co-NP upper bound together with explicit constructions for the two-player case. These are concrete, falsifiable contributions that build on standard graph-game techniques (counters for energy, positional strategies for mean-payoff) without introducing free parameters or circular definitions. The provision of effective constructions is a particular strength.

minor comments (2)

[Abstract] Abstract: the phrase 'effective constructions' is used without indicating whether the strategies are computable in polynomial time, exponential time, or only recursively; a brief clarification would help readers assess the algorithmic content of the result.
[Introduction / Preliminaries] The manuscript would benefit from an explicit statement, early in the introduction or preliminaries, of the precise definition of the two-dimensional weight vectors and the exact semantics of the combined energy/mean-payoff objective (e.g., whether the energy constraint is strict or weak).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments appear in the report, so we provide no point-by-point responses below.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper establishes memory requirements and complexity bounds for energy mean-payoff games on finite directed graphs with 2D integer weights. The one-player case is shown solvable in polynomial time and the two-player case placed in co-NP via explicit strategy constructions; these rest on standard techniques for multi-objective graph games (energy counters and mean-payoff positional strategies) rather than any self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. No equations or reductions in the abstract or stated claims collapse the results to their own inputs by construction. The distinction that the protagonist may require infinite memory while the antagonist requires none follows directly from the game objectives without circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract provides no explicit free parameters, invented entities, or non-standard axioms; the work relies on the standard formalization of graph games with vector weights.

axioms (1)

domain assumption Finite directed graphs with integer 2-dimensional edge weights form the underlying model.
Standard setup for the class of games studied; invoked implicitly by the problem definition.

pith-pipeline@v0.9.0 · 5668 in / 1279 out tokens · 35950 ms · 2026-05-25T10:36:15.201112+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · 1 internal anchor

[1]

1 P. A. Abdulla, M. F. Atig, P. Hofman, R. Mayr, K. N. Kumar, and P. Totzke. Inﬁnite-state energy games. In Henzinger and Miller [27], pages 7:1–7:10. V. Bruyère, Q. Hautem, M. Randour, and J.-F. Raskin XX:27 2 P. A. Abdulla, R. Mayr, A. Sangnier, and J. Sproston. Solving parity games on integer vectors. In P. R. D’Argenio and H. C. Melgratti, editors,CON...

work page 2013
[2]

Batterytransitionsystems

4 U.Boker, T.A.Henzinger, andA.Radhakrishna. Batterytransitionsystems. InS.Jagannathan and P. Sewell, editors,The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14, San Diego, CA, USA, January 20-21, 2014, pages 595–606. ACM,

work page 2014
[3]

Bouyer, U

5 P. Bouyer, U. Fahrenberg, K. G. Larsen, N. Markey, and J. Srba. Inﬁnite runs in weighted timed automata with energy constraints. In F. Cassez and C. Jard, editors,Formal Modeling and Analysis of Timed Systems, 6th International Conference, FORMATS 2008, Saint Malo, France, September 15-17, 2008, Proceedings, volume 5215 of Lecture Notes in Computer Scie...

work page 2008
[4]

Bouyer, P

6 P. Bouyer, P. Hofman, N. Markey, M. Randour, and M. Zimmermann. Bounding average- energy games. In J. Esparza and A. S. Murawski, editors,Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden,...

work page 2017
[5]

Brázdil, K

8 T. Brázdil, K. Chatterjee, A. Kucera, and P. Novotný. Eﬃcient controller synthesis for consumption games with multiple resource types. In P. Madhusudan and S. A. Seshia, editors, Computer Aided Veriﬁcation - 24th International Conference, CAV 2012, Berkeley, CA, USA, July 7-13, 2012, Proceedings, volume 7358 ofLecture Notes in Computer Science, pages 23...

work page 2012
[6]

Reachability Games on Extended Vector Addition Systems with States

9 T. Brázdil, P. Jancar, and A. Kucera. Reachability games on extended vector addition systems with states. CoRR, abs/1002.2557,

work page internal anchor Pith review Pith/arXiv arXiv
[7]

Brázdil, D

10 T. Brázdil, D. Klaska, A. Kucera, and P. Novotný. Minimizing running costs in consumption systems. In A. Biere and R. Bloem, editors,Computer Aided Veriﬁcation - 26th International Conference, CAV 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 18-22, 2014, Proceedings, volume 8559 ofLecture Notes in Computer Science, ...

work page 2014
[8]

Brázdil, A

11 T. Brázdil, A. Kucera, and P. Novotný. Optimizing the expected mean payoﬀ in energy markov decision processes. In C. Artho, A. Legay, and D. Peled, editors,Automated Technology for Veriﬁcation and Analysis - 14th International Symposium, ATVA 2016, Chiba, Japan, October 17-20, 2016, Proceedings, volume 9938 ofLecture Notes in Computer Science, pages 32–49,

work page 2016
[9]

13 V. Bruyère. Computer aided synthesis: A game-theoretic approach. In É. Charlier, J. Leroy, and M. Rigo, editors,Developments in Language Theory - 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings, volume 10396 ofLecture Notes in Computer Science, pages 3–35. Springer,

work page 2017
[10]

Bruyère, Q

14 V. Bruyère, Q. Hautem, and J. Raskin. On the complexity of heterogeneous multidimensional games. In J. Desharnais and R. Jagadeesan, editors, 27th International Conference on Concurrency Theory, CONCUR 2016, August 23-26, 2016, Québec City, Canada, volume 59 of LIPIcs, pages 11:1–11:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,

work page 2016
[11]

Chakrabarti, L

XX:28 Energy mean-payoﬀ games 15 A. Chakrabarti, L. de Alfaro, T. A. Henzinger, and M. Stoelinga. Resource interfaces. In R. Alur and I. Lee, editors,Embedded Software, Third International Conference, EMSOFT 2003, Philadelphia, PA, USA, October 13-15, 2003, Proceedings, volume 2855 ofLecture Notes in Computer Science, pages 117–133. Springer,

work page 2003
[12]

Chatterjee, L

17 K. Chatterjee, L. Doyen, T. A. Henzinger, and J. Raskin. Generalized mean-payoﬀ and energy games. In K. Lodaya and M. Mahajan, editors,IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, volume 8 ofLIPIcs, pages 505–516. Schloss Dagstuhl - Leibniz-Zentrum fue...

work page 2010
[13]

Chatterjee, T

19 K. Chatterjee, T. A. Henzinger, and M. Jurdzinski. Mean-payoﬀ parity games. In20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26-29 June 2005, Chicago, IL, USA, Proceedings, pages 178–187. IEEE Computer Society,

work page 2005
[14]

Daviaud, M

23 L. Daviaud, M. Jurdzinski, and R. Lazic. A pseudo-quasi-polynomial algorithm for mean-payoﬀ parity games. In A. Dawar and E. Grädel, editors,Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 325–334. ACM,

work page 2018
[15]

Fahrenberg, L

25 U. Fahrenberg, L. Juhl, K. G. Larsen, and J. Srba. Energy games in multiweighted automata. In A. Cerone and P. Pihlajasaari, editors,Theoretical Aspects of Computing - ICTAC 2011 - 8th International Colloquium, Johannesburg, South Africa, August 31 - September 2, 2011, Proceedings, volume 6916 ofLecture Notes in Computer Science, pages 95–115. Springer,

work page 2011
[16]

Gimbert and W

26 H. Gimbert and W. Zielonka. Games where you can play optimally without any memory. In M. Abadi and L. de Alfaro, editors,CONCUR 2005 - Concurrency Theory, 16th International Conference, CONCUR 2005, San Francisco, CA, USA, August 23-26, 2005, Proceedings, volume 3653 ofLecture Notes in Computer Science, pages 428–442. Springer,

work page 2005
[17]

Jurdzinski, R

29 M. Jurdzinski, R. Lazic, and S. Schmitz. Fixed-dimensional energy games are in pseudo- polynomial time. In M. M. Halldórsson, K. Iwama, N. Kobayashi, and B. Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 ofLecture Notes in Computer Sc...

work page 2015
[18]

Bruyère, Q

V. Bruyère, Q. Hautem, M. Randour, and J.-F. Raskin XX:29 31 S. R. Kosaraju and G. F. Sullivan. Detecting cycles in dynamic graphs in polynomial time (preliminary version). In J. Simon, editor,Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 398–406. ACM,

work page 1988
[19]

32 A. Kucera. Playing games with counter automata. In A. Finkel, J. Leroux, and I. Potapov, editors, Reachability Problems - 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012, Proceedings, volume 7550 ofLecture Notes in Computer Science, pages 29–41. Springer,

work page 2012
[20]

Pnueli and R

33 A. Pnueli and R. Rosner. On the synthesis of an asynchronous reactive module. In G. Ausiello, M. Dezani-Ciancaglini, and S. R. D. Rocca, editors,Automata, Languages and Programming, 16th International Colloquium, ICALP89, Stresa, Italy, July 11-15, 1989, Proceedings, volume 372 ofLecture Notes in Computer Science, pages 652–671. Springer,

work page 1989
[21]

34 Y. Velner. Robust multidimensional mean-payoﬀ games are undecidable. In A. M. Pitts, editor, Foundations of Software Science and Computation Structures - 18th International Conference, FoSSaCS 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015, Proceedings, volume 9034 ofLe...

work page 2015
[22]

Zwick and M

36 U. Zwick and M. Paterson. The complexity of mean payoﬀ games on graphs.Theoretical Computer Science, 158(1-2):343–359, 1996

work page 1996

[1] [1]

1 P. A. Abdulla, M. F. Atig, P. Hofman, R. Mayr, K. N. Kumar, and P. Totzke. Inﬁnite-state energy games. In Henzinger and Miller [27], pages 7:1–7:10. V. Bruyère, Q. Hautem, M. Randour, and J.-F. Raskin XX:27 2 P. A. Abdulla, R. Mayr, A. Sangnier, and J. Sproston. Solving parity games on integer vectors. In P. R. D’Argenio and H. C. Melgratti, editors,CON...

work page 2013

[2] [2]

Batterytransitionsystems

4 U.Boker, T.A.Henzinger, andA.Radhakrishna. Batterytransitionsystems. InS.Jagannathan and P. Sewell, editors,The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14, San Diego, CA, USA, January 20-21, 2014, pages 595–606. ACM,

work page 2014

[3] [3]

Bouyer, U

5 P. Bouyer, U. Fahrenberg, K. G. Larsen, N. Markey, and J. Srba. Inﬁnite runs in weighted timed automata with energy constraints. In F. Cassez and C. Jard, editors,Formal Modeling and Analysis of Timed Systems, 6th International Conference, FORMATS 2008, Saint Malo, France, September 15-17, 2008, Proceedings, volume 5215 of Lecture Notes in Computer Scie...

work page 2008

[4] [4]

Bouyer, P

6 P. Bouyer, P. Hofman, N. Markey, M. Randour, and M. Zimmermann. Bounding average- energy games. In J. Esparza and A. S. Murawski, editors,Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden,...

work page 2017

[5] [5]

Brázdil, K

8 T. Brázdil, K. Chatterjee, A. Kucera, and P. Novotný. Eﬃcient controller synthesis for consumption games with multiple resource types. In P. Madhusudan and S. A. Seshia, editors, Computer Aided Veriﬁcation - 24th International Conference, CAV 2012, Berkeley, CA, USA, July 7-13, 2012, Proceedings, volume 7358 ofLecture Notes in Computer Science, pages 23...

work page 2012

[6] [6]

Reachability Games on Extended Vector Addition Systems with States

9 T. Brázdil, P. Jancar, and A. Kucera. Reachability games on extended vector addition systems with states. CoRR, abs/1002.2557,

work page internal anchor Pith review Pith/arXiv arXiv

[7] [7]

Brázdil, D

10 T. Brázdil, D. Klaska, A. Kucera, and P. Novotný. Minimizing running costs in consumption systems. In A. Biere and R. Bloem, editors,Computer Aided Veriﬁcation - 26th International Conference, CAV 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 18-22, 2014, Proceedings, volume 8559 ofLecture Notes in Computer Science, ...

work page 2014

[8] [8]

Brázdil, A

11 T. Brázdil, A. Kucera, and P. Novotný. Optimizing the expected mean payoﬀ in energy markov decision processes. In C. Artho, A. Legay, and D. Peled, editors,Automated Technology for Veriﬁcation and Analysis - 14th International Symposium, ATVA 2016, Chiba, Japan, October 17-20, 2016, Proceedings, volume 9938 ofLecture Notes in Computer Science, pages 32–49,

work page 2016

[9] [9]

13 V. Bruyère. Computer aided synthesis: A game-theoretic approach. In É. Charlier, J. Leroy, and M. Rigo, editors,Developments in Language Theory - 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings, volume 10396 ofLecture Notes in Computer Science, pages 3–35. Springer,

work page 2017

[10] [10]

Bruyère, Q

14 V. Bruyère, Q. Hautem, and J. Raskin. On the complexity of heterogeneous multidimensional games. In J. Desharnais and R. Jagadeesan, editors, 27th International Conference on Concurrency Theory, CONCUR 2016, August 23-26, 2016, Québec City, Canada, volume 59 of LIPIcs, pages 11:1–11:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,

work page 2016

[11] [11]

Chakrabarti, L

XX:28 Energy mean-payoﬀ games 15 A. Chakrabarti, L. de Alfaro, T. A. Henzinger, and M. Stoelinga. Resource interfaces. In R. Alur and I. Lee, editors,Embedded Software, Third International Conference, EMSOFT 2003, Philadelphia, PA, USA, October 13-15, 2003, Proceedings, volume 2855 ofLecture Notes in Computer Science, pages 117–133. Springer,

work page 2003

[12] [12]

Chatterjee, L

17 K. Chatterjee, L. Doyen, T. A. Henzinger, and J. Raskin. Generalized mean-payoﬀ and energy games. In K. Lodaya and M. Mahajan, editors,IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, volume 8 ofLIPIcs, pages 505–516. Schloss Dagstuhl - Leibniz-Zentrum fue...

work page 2010

[13] [13]

Chatterjee, T

19 K. Chatterjee, T. A. Henzinger, and M. Jurdzinski. Mean-payoﬀ parity games. In20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26-29 June 2005, Chicago, IL, USA, Proceedings, pages 178–187. IEEE Computer Society,

work page 2005

[14] [14]

Daviaud, M

23 L. Daviaud, M. Jurdzinski, and R. Lazic. A pseudo-quasi-polynomial algorithm for mean-payoﬀ parity games. In A. Dawar and E. Grädel, editors,Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 325–334. ACM,

work page 2018

[15] [15]

Fahrenberg, L

25 U. Fahrenberg, L. Juhl, K. G. Larsen, and J. Srba. Energy games in multiweighted automata. In A. Cerone and P. Pihlajasaari, editors,Theoretical Aspects of Computing - ICTAC 2011 - 8th International Colloquium, Johannesburg, South Africa, August 31 - September 2, 2011, Proceedings, volume 6916 ofLecture Notes in Computer Science, pages 95–115. Springer,

work page 2011

[16] [16]

Gimbert and W

26 H. Gimbert and W. Zielonka. Games where you can play optimally without any memory. In M. Abadi and L. de Alfaro, editors,CONCUR 2005 - Concurrency Theory, 16th International Conference, CONCUR 2005, San Francisco, CA, USA, August 23-26, 2005, Proceedings, volume 3653 ofLecture Notes in Computer Science, pages 428–442. Springer,

work page 2005

[17] [17]

Jurdzinski, R

29 M. Jurdzinski, R. Lazic, and S. Schmitz. Fixed-dimensional energy games are in pseudo- polynomial time. In M. M. Halldórsson, K. Iwama, N. Kobayashi, and B. Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 ofLecture Notes in Computer Sc...

work page 2015

[18] [18]

Bruyère, Q

V. Bruyère, Q. Hautem, M. Randour, and J.-F. Raskin XX:29 31 S. R. Kosaraju and G. F. Sullivan. Detecting cycles in dynamic graphs in polynomial time (preliminary version). In J. Simon, editor,Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 398–406. ACM,

work page 1988

[19] [19]

32 A. Kucera. Playing games with counter automata. In A. Finkel, J. Leroux, and I. Potapov, editors, Reachability Problems - 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012, Proceedings, volume 7550 ofLecture Notes in Computer Science, pages 29–41. Springer,

work page 2012

[20] [20]

Pnueli and R

33 A. Pnueli and R. Rosner. On the synthesis of an asynchronous reactive module. In G. Ausiello, M. Dezani-Ciancaglini, and S. R. D. Rocca, editors,Automata, Languages and Programming, 16th International Colloquium, ICALP89, Stresa, Italy, July 11-15, 1989, Proceedings, volume 372 ofLecture Notes in Computer Science, pages 652–671. Springer,

work page 1989

[21] [21]

34 Y. Velner. Robust multidimensional mean-payoﬀ games are undecidable. In A. M. Pitts, editor, Foundations of Software Science and Computation Structures - 18th International Conference, FoSSaCS 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015, Proceedings, volume 9034 ofLe...

work page 2015

[22] [22]

Zwick and M

36 U. Zwick and M. Paterson. The complexity of mean payoﬀ games on graphs.Theoretical Computer Science, 158(1-2):343–359, 1996

work page 1996