Pith. sign in

REVIEW 4 minor 52 references

Simplicity Lies in the Eye of the Beholder: A Strategic Perspective on Controllers in Reactive Synthesis

T0 review · 0 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Strategy complexity in reactive synthesis is not an intrinsic property of a strategy: the paper argues the standard Mealy-machine measure is representation-dependent and can misorder how simple controllers really are.

desk verdict Solid, honest survey of memory/randomness complexity; the Section 5 representation-dependence argument is the memorable part, but it's a position statement, not a formal theory. read the letter →

arxiv 2509.04129 v1 pith:Z7HDTKJ7 submitted 2025-09-04 cs.LO cs.AIcs.FLmath.PR

Mickael Randour This is my paper
classification cs.LOcs.AIcs.FLmath.PR MSC 68Q6091A5003D05
keywords reactivesynthesisstrategycomplexityMealymachinesgamesongraphsfinitememoryrandomizedstrategiesmulti-objectivecontroller
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper argues that the standard way of measuring strategy complexity in reactive synthesis—counting the memory states in a Mealy machine—is representation-dependent and can misrepresent how simple a controller actually is to explain, verify, and implement. It surveys recent results showing when memory and randomness are needed for optimal play in games on graphs, including a finite-memory analogue of the classical memoryless determinacy characterization and a strict taxonomy of randomized finite-memory strategies. The core plea is for a representation-agnostic theory of strategy complexity, where a controller's true cost is assessed independently of the particular machine format used to encode it. If the claim holds, ranking strategies by Mealy-state count, a widespread practice, may send synthesis in the wrong direction.

What carries the argument

The load-bearing object is the Mealy machine model of a strategy (memory states plus a next-action function and an update function), which the paper argues is the source of the apparent complexity: by flattening data structures like counters into distinct states, it inflates complexity, while treating irregular lookup tables as equally simple. For the technical results on memory, the key tool is the arena-independent chromatic memory structure, whose monotonicity and selectivity conditions characterize when strategies based on that memory suffice for both players and yield one-to-two-player lifts.

What would settle it

A computed falsifier: define a formal 'program complexity' for strategies, say the size of a while-loop-plus-counter program that computes the next action, and check whether minimal Mealy-state size and minimal program size diverge on a family of games. The paper's energy-Büchi example predicts an exponential gap; proving that for every omega-regular objective the two measures are polynomially related would refute the representation-dependence claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that 'simplicity' of a strategy is not an intrinsic property: it depends on the representation. Under the standard Mealy-machine model, all memoryless strategies count as equally simple, yet two single-state strategies can differ widely in how easy they are to explain or implement; conversely, a strategy that cycles in a state N times before moving looks pseudo-polynomial in Mealy states but is naturally a one-counter program. The paper supports this with a review of results: arena-independent chromatic memory structures characterize when finite-memory strategies suffice for both players, with one-to-two-player lifts; chromatic finite-memory strategies characteri

Load-bearing premise

The load-bearing premise is that 'practical simplicity'—how easy a strategy is to explain, verify, and implement—is a meaningful property that can be discussed without a formal definition; if it cannot be made precise, the paper's call for a representation-agnostic theory lacks a well-defined target.

Editorial extensions

If this is right

  • If the standard measure is model-dependent, minimizing Mealy-state count can misorder strategies that are simple in practice; controller synthesis should compare representations, not just machines.
  • Finite-memory determinacy lifts from one-player to two-player games exactly when objectives are monotone and selective with respect to an arena-independent chromatic memory structure.
  • In stochastic games, the same arena-independent finite-memory techniques lift optimal play from MDPs to stochastic games.
  • A winning condition admits chromatic finite-memory strategies in every infinite arena exactly when it is omega-regular, tying strategy memory to automata-theoretic regularity.
  • Under finite memory, behavioral, mixed, and general randomized strategies form a strict expressiveness hierarchy; the classical equivalence between behavioral and mixed strategies collapses.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable extension is a formal cost model for strategies as programs (counters, loops, trees) and a systematic comparison of description length against Mealy-state count across synthesis benchmarks; the paper's examples suggest the rankings would diverge.
  • Existing lower bounds stated in Mealy states, such as 'exponential memory required,' may overstate practical difficulty for objectives with structured data representations; reinterpreted as program-size bounds, some may collapse.
  • A representation-agnostic theory would likely need to treat interpretability as a cost dimension, which cannot be settled by expressiveness alone; the paper leaves that formalization open.
  • The decision-tree and enriched-Mealy alternatives point to an analogy with data structures in algorithm design: complexity should be measured on the structure actually used, not on a flattened encoding.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. This invited survey addresses the complexity of winning and optimal strategies in game-theoretic controller synthesis. It recalls the basic game models, objectives, and the standard Mealy-machine representation of strategies. Sections 3 and 4 summarize recent results on memory and randomized strategies, including a characterization of finite-memory determinacy via arena-independent chromatic memory structures, a one-to-two-player lift, a characterization of omega-regularity via finite-memory determinacy on infinite arenas, and a complete taxonomy of randomized finite-memory strategies. Section 5 argues that the usual measure of complexity—number of Mealy memory states—is representation-dependent: it gives a memoryless strategy whose intuitive simplicity is not reflected in its single-state encoding, and a counter-based strategy whose Mealy encoding needs N+1 states but is simple in a programmatic representation. The paper advocates studying alternative representations (decision trees, strategy machines, enriched Mealy machines, programs, neural networks) and developing a representation-agnostic complexity theory.

Significance. If the thesis of Section 5 is adopted, it would push the community to reconsider rankings of strategies based solely on Mealy-state counting and to develop richer complexity measures that reflect implementation, explanation, and verification effort. The survey's main contribution is organizational and programmatic rather than theorem-based; it condenses a significant body of recent work, including the author's own results on memory and randomized strategies, into an accessible narrative. It cites primary sources for all formal statements and is candid about its informal treatment. The examples in Section 5 effectively demonstrate that the Mealy-state measure can be representation-relative, although the stronger normative conclusion about 'practical simplicity' rests on an informal notion that the paper itself does not formalize. This is a limitation, but an openly acknowledged one for a position-style invited survey.

minor comments (4)
  1. [Section 5, Fig. 8] The claim that the counter-based strategy is 'easily implementable with a simple counter' would be strengthened by an explicit sentence distinguishing the mathematical fact (the number of Mealy states is representation-dependent) from the informal judgment about practical simplicity. As written, the normative reading is clear but the criteria for 'practical simplicity' are left implicit. I suggest adding one paragraph stating that no formal definition is intended and that a formal treatment is left for future work.
  2. [Section 1, Outline] The warning about informality is useful. Since Section 5 introduces the phrase 'practical simplicity' without a definition, consider placing a similar caveat there.
  3. [Section 5, first paragraph] Minor typo: 'N + 1distinct' should be 'N + 1 distinct'.
  4. [Section 4, Fig. 5] The taxonomy diagram is presented without mentioning that the inclusions are proved in [41]. Adding a one-line pointer adjacent to the figure would help readers who are not familiar with the source.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: survey's position argument is grounded in examples and disclosed as informal.

full rationale

This paper is an invited survey and position note, not a formal derivation. The central claim of Section 5—that Mealy-machine state count can misrepresent practical simplicity—is supported by two self-contained examples (Fig. 8): a one-state Mealy machine that hides structural differences between memoryless strategies, and an energy-Büchi game whose N+1 Mealy states correspond to a simple counter. These examples do not depend on the self-cited technical theorems [9,11,13,41,42]; they are presented as illustrative observations about representation choice. The self-cited results are external, published theorems with stated assumptions, and the paper explicitly warns that it adopts an informal approach with pointers to full formal details (Section 1, Outline). No parameter is fitted and then renamed as a prediction, and no definition of simplicity is constructed in terms of the conclusion. The acknowledged lack of a formal definition of 'practical simplicity' is a limitation of the position argument, but it is a correctness/scope issue, not circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The survey contains no new technical construction. All axioms are background assumptions from the cited literature or standard modeling choices for games on graphs. No free parameters or invented entities appear because the paper is an exposition.

assumptions (5)
  • domain assumption Two-player turn-based games on finite graphs are an adequate model for controller-environment interaction.
    Section 2 frames the entire survey around this model; it is cited to the textbook [32] rather than justified in the paper.
  • domain assumption The number of states in a Mealy machine is the classical measure of strategy complexity.
    Sections 2 and 3 use this as the working definition of memory, noting that it is 'often treated as canonical' in the literature.
  • standard math Gimbert and Zielonka's characterization of memoryless-determined games and its one-to-two-player lift are correct.
    Theorems 1 and Corollary 1 in Section 3 rely on [35] as a foundation for the finite-memory investigations.
  • standard math Kuhn's theorem and its generalizations: behavioral, mixed, and general randomized strategies coincide under perfect recall.
    Section 4 uses this classical equivalence as background to frame the finite-memory taxonomy, citing [2,3].
  • standard math All omega-regular winning conditions admit finite-memory optimal strategies in every infinite arena, and the converse holds via the construction in [13].
    Theorem 3 in Section 3 depends on these prior results from [44,52] and the author's own [13].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Simplicity Lies in the Eye of the Beholder: A Strategic Perspective on Controllers in Reactive Synthesis." pith.science (2026). https://pith.science/paper/Z7HDTKJ7

@misc{pith2026250904129,
  author       = {Pith},
  title        = {Pith review of: Simplicity Lies in the Eye of the Beholder: A Strategic Perspective on Controllers in Reactive Synthesis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z7HDTKJ7}},
  note         = {Machine review of arXiv:2509.04129}
}
read the original abstract

In the game-theoretic approach to controller synthesis, we model the interaction between a system to be controlled and its environment as a game between these entities, and we seek an appropriate (e.g., winning or optimal) strategy for the system. This strategy then serves as a formal blueprint for a real-world controller. A common belief is that simple (e.g., using limited memory) strategies are better: corresponding controllers are easier to conceive and understand, and cheaper to produce and maintain. This invited contribution focuses on the complexity of strategies in a variety of synthesis contexts. We discuss recent results concerning memory and randomness, and take a brief look at what lies beyond our traditional notions of complexity for strategies.

Figures

Figures reproduced from arXiv: 2509.04129 by the authors.

Figure 1
Figure 1. Three types of games. Vertices are partitioned between those of [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Memory is needed to see a and b infinitely often. A winning strategy for P⃝ is given as a two-state Mealy machine. Multiple objectives. Complex objectives arise when combining simple ones, and they usually require more complex strategies to play optimally. Consider the simple (one-player) game depicted in Figure 2a: the objective of P⃝ is to see both colors a and b infinitely often. This generalized Büchi objective … view at source ↗
Figure 3
Figure 3. A chromatic memory that suffices for W = Buchi(a)∩Buchi(b) in all finite arenas. This led us to define a new fron￾tier: understanding the limits of one-to￾two-player lifts. We introduced arena￾independent chromatic memory structures as suitable tools for this task. Let us re￾visit the generalized Büchi example. As￾sume C = {a, b, c} and consider the win￾ning condition W = Buchi(a) ∩ Buchi(b), which requires both col… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Randomness is nec￾essary to see a and b with non-zero probability. Introducing randomness. We may need randomness to deal with, e.g., multiple objectives, concurrent games, or imperfect information [32]. Consider the example in [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: Taxonomy of randomized finite￾memory strategy classes. In joint work with Main [41], we established a complete taxonomy of these strategy classes, illustrated in [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 6
Figure 6. Figure 6: From home, take the train or bike to reach work. Payoff sets. Consider the multi-objective MDP in [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: Achievable payoff set. We depict this set in [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: Strategy complexity is representation-dependent. [PITH_FULL_IMAGE:figures/full_fig_p013_8.png]
Figure 9
Figure 9. Figure 9: Decision tree to reach (0, 0) in a 2D grid. A well-studied alternative is the use of decision trees (DTs), particularly suited to highly structured state and action spaces [14,15]. DTs have primar￾ily been used to compactly represent memoryless strategies, serving as a…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

52 extracted references · 31 canonical work pages

  1. [1]

    In: Censor-Hillel, K.,Grandoni,F.,Ouaknine,J.,Puppis,G.(eds.)52ndInternationalColloquiumon Automata, Languages, and Programming, ICALP 2025, July 8-11, 2025, Aarhus, Denmark

    Ajdarów, M., Main, J.C.A., Novotný, P., Randour, M.: Taming infinity one chunk at a time: Concisely represented strategies in one-counter MDPs. In: Censor-Hillel, K.,Grandoni,F.,Ouaknine,J.,Puppis,G.(eds.)52ndInternationalColloquiumon Automata, Languages, and Programming, ICALP 2025, July 8-11, 2025, Aarhus, Denmark. LIPIcs, vol. 334, pp. 138:1–138:19. Sc...

    work page doi:10.4230/lipics.icalp.2025.138 2025

  2. [2]

    In: Dresher, M., Shapley, L.S., Tucker, A.W

    Aumann, R.J..: Mixed and behavior strategies in infinite extensive games. In: Dresher, M., Shapley, L.S., Tucker, A.W. (eds.) Advances in Game Theory. (AM- 52), Volume 52, pp. 627–650. Princeton University Press (1964). https://doi.org/ 10.1515/9781400882014-029

    work page doi:10.1515/9781400882014-029 1964

  3. [3]

    Bertrand, N., Genest, B., Gimbert, H.: Qualitative determinacy and decidability of stochastic games with signals. J. ACM64(5), 33:1–33:48 (2017). https://doi. org/10.1145/3107926

    work page doi:10.1145/3107926 2017

  4. [4]

    Bianco, A., Faella, M., Mogavero, F., Murano, A.: Exploring the boundary of half- positionality. Ann. Math. Artif. Intell.62(1-2), 55–77 (2011). https://doi.org/10. 1007/S10472-011-9250-1

    work page 2011

  5. [5]

    In: A Strategic Perspective on Controllers in Reactive Synthesis 15 Lahiri, S.K., Wang, C

    Blahoudek, F., Brázdil, T., Novotný, P., Ornik, M., Thangeda, P., Topcu, U.: Qualitative controller synthesis for consumption Markov decision processes. In: A Strategic Perspective on Controllers in Reactive Synthesis 15 Lahiri, S.K., Wang, C. (eds.) Computer Aided Verification - 32nd International Conference, CAV 2020, Los Angeles, CA, USA, July 21-24, 2...

    work page doi:10.1007/978-3-030-53291 2020

  6. [6]

    In: Clarke, E.M., Henzinger, T.A., Veith, H., Bloem, R

    Bloem, R., Chatterjee, K., Jobstmann, B.: Graph games and reactive syn- thesis. In: Clarke, E.M., Henzinger, T.A., Veith, H., Bloem, R. (eds.) Hand- book of Model Checking, pp. 921–962. Springer (2018). https://doi.org/10.1007/ 978-3-319-10575-8_27

    work page 2018

  7. [7]

    Bouyer, P., Casares, A., Randour, M., Vandenhove, P.: Half-positional objectives recognized by deterministic Büchi automata. Log. Methods Comput. Sci.20(3) (2024). https://doi.org/10.46298/LMCS-20(3:19)2024

    work page doi:10.46298/lmcs-20(3:19)2024 2024

  8. [8]

    (eds.) 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany

    Bouyer, P., Fijalkow, N., Randour, M., Vandenhove, P.: How to play optimally for regular objectives? In: Etessami, K., Feige, U., Puppis, G. (eds.) 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany. LIPIcs, vol. 261, pp. 118:1–118:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2...

    doi:10.4230/lipics.icalp 2023

Show all 52 references
  1. [9]

    Bouyer, P., Le Roux, S., Oualhadj, Y., Randour, M., Vandenhove, P.: Games where you can play optimally with arena-independent finite memory. Log. Methods Com- put. Sci. 18(1) (2022). https://doi.org/10.46298/LMCS-18(1:11)2022

    2022 doi

  2. [10]

    Acta Informatica 55(2), 91–127 (2018)

    Bouyer, P., Markey, N., Randour, M., Larsen, K.G., Laursen, S.: Average- energy games. Acta Informatica 55(2), 91–127 (2018). https://doi.org/10.1007/ S00236-016-0274-1

    2018

  3. [11]

    Bouyer, P., Oualhadj, Y., Randour, M., Vandenhove, P.: Arena-independent finite- memory determinacy in stochastic games. Log. Methods Comput. Sci. 19(4) (2023). https://doi.org/10.46298/LMCS-19(4:18)2023

    2023 doi

  4. [13]

    Bouyer,P.,Randour,M.,Vandenhove,P.:Characterizingomega-regularitythrough finite-memorydeterminacyofgamesoninfinitegraphs.TheoretiCS 2(2023).https: //doi.org/10.46298/THEORETICS.23.1

    2023 doi

  5. [14]

    In: Kroening, D., Pasareanu, C.S

    Brazdil, T., Chatterjee, K., Chmelik, M., Fellner, A., Kretinsky, J.: Counterex- ample explanation by learning small strategies in Markov decision processes. In: Kroening, D., Pasareanu, C.S. (eds.) Computer Aided Verification - 27th Interna- tional Conference, CAV 2015, San F...

    2015 doi

  6. [15]

    In: Beyer, D., Huisman, M

    Brazdil, T., Chatterjee, K., Kretinsky, J., Toman, V.: Strategy representation by decision trees in reactive synthesis. In: Beyer, D., Huisman, M. (eds.) Tools and Algorithms for the Construction and Analysis of Systems - 24th International Con- ference, TACAS 2018, Held as Pa...

    2018

  7. [16]

    Brihaye, T., Delgrange, F., Oualhadj, Y., Randour, M.: Life is random, time is not: Markov decision processes with window objectives. Log. Methods Comput. Sci. 16(4) (2020). https://doi.org/10.23638/LMCS-16(4:13)2020

    2020 doi

  8. [17]

    Brihaye, T., Goeminne, A., Main, J.C.A., Randour, M.: Reachability games and friends:Ajourneythroughthelensofmemoryandcomplexity.In:Bouyer,P.,Srini- vasan, S. (eds.) 43rd IARCS Annual Conference on Foundations of Software Tech- nology and Theoretical Computer Science, FSTTCS 2...

    2023 doi

  9. [18]

    In: Cantone, D., Delzanno, G

    Bruyère, V., Hautem, Q., Randour, M.: Window parity games: an alternative ap- proach toward parity games with time bounds. In: Cantone, D., Delzanno, G. (eds.) Proceedings of the Seventh International Symposium on Games, Automata, Log- ics and Formal Verification, GandALF 2016...

    2016 doi

  10. [19]

    In: Fokkink, W.J., van Glabbeek, R

    Bruyère, V., Hautem, Q., Randour, M., Raskin, J.F.: Energy mean-payoff games. In: Fokkink, W.J., van Glabbeek, R. (eds.) 30th International Conference on Con- currency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Nether- lands. LIPIcs, vol. 140, pp. 21:1–21:17. Schl...

    2019 doi

  11. [20]

    Bruyère, V., Filiot, E., Randour, M., Raskin, J.F.: Meet your expectations with guarantees: Beyond worst-case synthesis in quantitative games. Inf. Comput.254, 259–295 (2017). https://doi.org/10.1016/J.IC.2016.10.011

    2017 doi

  12. [21]

    In: Bessiere, C

    Carr, S., Jansen, N., Topcu, U.: Verifiable RNN-based policies for POMDPs under temporal logic constraints. In: Bessiere, C. (ed.) Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020. pp. 4121–

    2020

  13. [22]

    In: Sobocinski, P., Lago, U.D., Esparza, J

    Casares, A., Ohlmann, P.: Positionalω-regular languages. In: Sobocinski, P., Lago, U.D., Esparza, J. (eds.) Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, July 8-11, 2024. pp. 21:1–21:14. ACM (2024). https://doi.org...

    2024

  14. [23]

    Casares, A., Ohlmann, P.: Characterising memory in infinite games. Log. Methods Comput. Sci. 21(1) (2025). https://doi.org/10.46298/LMCS-21(1:28)2025

    2025 doi

  15. [24]

    In: 1st International Conference on Quantitative Evaluation of Systems (QEST 2004), 27-30 September 2004, Enschede, The Netherlands

    Chatterjee, K., de Alfaro, L., Henzinger, T.A.: Trading memory for randomness. In: 1st International Conference on Quantitative Evaluation of Systems (QEST 2004), 27-30 September 2004, Enschede, The Netherlands. pp. 206–217. IEEE Computer Society (2004). https://doi.org/10.110...

    2004 arXiv

  16. [25]

    Chatterjee, K., Doyen, L., Gimbert, H., Henzinger, T.A.: Randomness for free. Inf. Comput. 245, 3–16 (2015). https://doi.org/10.1016/J.IC.2015.06.003

    2015 doi

  17. [26]

    Chatterjee, K., Doyen, L., Randour, M., Raskin, J.F.: Looking at mean-payoff and total-payoff through windows. Inf. Comput.242, 25–52 (2015). https://doi.org/ 10.1016/J.IC.2015.03.010

    2015 doi

  18. [27]

    In: Egerstedt, M., Mishra, B

    Chatterjee, K., Henzinger, T.A., Prabhu, V.S.: Trading infinite memory for uni- form randomness in timed games. In: Egerstedt, M., Mishra, B. (eds.) Hybrid Systems: Computation and Control, 11th International Workshop, HSCC 2008, St. Louis, MO, USA, April 22-24, 2008. Proceedi...

    2008

  19. [28]

    Chatterjee,K.,Randour,M.,Raskin,J.F.:Strategysynthesisformulti-dimensional quantitativeobjectives.ActaInformatica 51(3-4),129–163(2014).https://doi.org/ 10.1007/S00236-013-0182-6 A Strategic Perspective on Controllers in Reactive Synthesis 17

    2014 doi

  20. [29]

    Summaries of the Summer Institute of Symbolic Logic1, 3–50 (1957)

    Church, A.: Applications of recursive arithmetic to the problem of circuit synthesis. Summaries of the Summer Institute of Symbolic Logic1, 3–50 (1957)

    1957

  21. [30]

    (eds.) Proceedings First Symposium on Games, Automata, Logic, and Formal Verification, GANDALF 2010, Minori (Amalfi Coast), Italy, 17-18th June 2010

    Cristau, J., David, C., Horn, F.: How do we remember the past in randomised strategies? In: Montanari, A., Napoli, M., Parente, M. (eds.) Proceedings First Symposium on Games, Automata, Logic, and Formal Verification, GANDALF 2010, Minori (Amalfi Coast), Italy, 17-18th June 20...

    2010 doi

  22. [31]

    In: Biere, A., Parker, D

    Delgrange, F., Katoen, J.P., Quatmann, T., Randour, M.: Simple strategies in multi-objective MDPs. In: Biere, A., Parker, D. (eds.) Tools and Algorithms for the Construction and Analysis of Systems - 26th International Conference, TACAS 2020, Held as Part of the European Joint...

    2020 doi

  23. [33]

    Gelderie, M.: Strategy machines: representation and complexity of strategies in in- finite games. Ph.D. thesis, RWTH Aachen University (2014), https://publications. rwth-aachen.de/record/229827/files/5025.pdf

    2014

  24. [34]

    Gimbert, H., Kelmendi, E.: Submixing and shift-invariant stochastic games. Int. J. Game Theory 52(4), 1179–1214 (2023). https://doi.org/10.1007/ S00182-023-00860-5

    2023

  25. [35]

    In: Abadi, M., de Alfaro, L

    Gimbert, H., Zielonka, W.: Games where you can play optimally without any memory. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005 - Concurrency Theory, 16th International Conference, CONCUR 2005, San Francisco, CA, USA, August 23-26, 2005, Proceedings. Lecture Notes in Compute...

    2005

  26. [36]

    (eds.): Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], Lecture Notes in Computer Science, vol

    Grädel, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], Lecture Notes in Computer Science, vol. 2500. Springer (2002). https://doi.org/ 10.1007/3-540-36387-4

    2001 doi

  27. [37]

    In: Albers, S., Marion, J.Y

    Horn, F.: Random fruits on the Zielonka tree. In: Albers, S., Marion, J.Y. (eds.) 26th International Symposium on Theoretical Aspects of Computer Science, STACS2009,February26-28,2009,Freiburg,Germany,Proceedings.LIPIcs,vol.3, pp. 541–552. Schloss Dagstuhl - Leibniz-Zentrum fü...

    2009

  28. [38]

    Kopczyński, E.: Half-positional Determinacy of Infinite Games. Ph.D. thesis, War- saw University (2008), https://www.mimuw.edu.pl/~erykk/papers/hpwc.pdf

    2008

  29. [39]

    In:Lomuscio,A.,Vardi,M.Y

    LeRoux,S.,Pauly,A.:Extendingfinitememorydeterminacytomultiplayergames. In:Lomuscio,A.,Vardi,M.Y. (eds.)Proceedingsofthe4thInternationalWorkshop on Strategic Reasoning, SR 2016, New York City, USA, 10th July 2016. EPTCS, vol. 218, pp. 27–40 (2016). https://doi.org/10.4204/EPTCS.218.3

    2016 doi

  30. [40]

    In: Ganguly, S., Pandya, P.K

    Le Roux, S., Pauly, A., Randour, M.: Extending finite-memory determinacy by Boolean combination of winning conditions. In: Ganguly, S., Pandya, P.K. (eds.) 38th IARCS Annual Conference on Foundations of Software Technology and The- oretical Computer Science, FSTTCS 2018, Decem...

    2018 doi

  31. [41]

    Main, J.C.A., Randour, M.: Different strokes in randomised strategies: Revisiting Kuhn’s theorem under finite-memory assumptions. Inf. Comput.301(2024). https: //doi.org/10.1016/J.IC.2024.105229

    2024

  32. [42]

    CoRR abs/2502.18296 (2025)

    Main, J.C.A., Randour, M.: Mixing any cocktail with limited ingredients: On the structure of payoff sets in multi-objective MDPs and its impact on ran- domised strategies. CoRR abs/2502.18296 (2025). https://doi.org/10.48550/ ARXIV.2502.18296, preprint

    2025 doi

  33. [43]

    Monmege, B., Parreaux, J., Reynier, P.A.: Playing stochastically in weighted timed games to emulate memory. Log. Methods Comput. Sci.21(1) (2025). https://doi. org/10.46298/LMCS-21(1:19)2025

    2025 doi

  34. [44]

    In: Skowron, A

    Mostowski, A.W.: Regular expressions for infinite trees and a standard form of automata. In: Skowron, A. (ed.) Computation Theory. pp. 157–168. Springer Berlin Heidelberg, Berlin, Heidelberg (1985)

    1985

  35. [45]

    In: Proceedings of the European Conference on Complex Systems 2012, ECCS 2012, Brussels, Belgium, September 2-7, 2012

    Randour, M.: Automated Synthesis of Reliable and Efficient Systems Through Game Theory: A Case Study. In: Proceedings of the European Conference on Complex Systems 2012, ECCS 2012, Brussels, Belgium, September 2-7, 2012. pp. 731–738. Springer Proceedings in Complexity, Springe...

    2012

  36. [46]

    In: Fijalkow, N

    Randour, M.: Games with multiple objectives. In: Fijalkow, N. (ed.) Games on Graphs: From Logic and Automata to Algorithms, pp. 488–527. Cambridge Uni- versity Press (2025). https://doi.org/10.48550/ARXIV.2305.10546, in press

    2025 doi arXiv

  37. [47]

    Proceedings

    Randour, M., Raskin, J.F., Sankur, O.: Variations on the stochastic shortest path problem.In:D’Souza,D.,Lal,A.,Larsen,K.G.(eds.)Verification,ModelChecking, and Abstract Interpretation - 16th International Conference, VMCAI 2015, Mum- bai, India, January 12-14, 2015. Proceeding...

    2015 doi

  38. [48]

    Formal Methods in System Design50(2-3), 207–248 (2017)

    Randour, M., Raskin, J.F., Sankur, O.: Percentile queries in multi-dimensional Markov decision processes. Formal Methods in System Design50(2-3), 207–248 (2017). https://doi.org/10.1007/S10703-016-0262-7

    2017 doi

  39. [49]

    In: Proceedings of the International AAAI Workshop on Generalization in Planning, GenPlan’25 (2025)

    Shabadi, G., Fijalkow, N., Matricon, T.: Programmatic reinforcement learning: Navigating gridworlds. In: Proceedings of the International AAAI Workshop on Generalization in Planning, GenPlan’25 (2025). https://doi.org/10.48550/ARXIV. 2402.11650

    2025 doi arXiv

  40. [50]

    In: de Alfaro, L

    Thomas, W.: Facets of synthesis: Revisiting Church’s problem. In: de Alfaro, L. (ed.) Foundations of Software Science and Computational Structures, 12th Interna- tional Conference, FOSSACS 2009, Held as Part of the Joint European Conferences on Theory and Practice of Software,...

    2009 doi

  41. [51]

    Velner, Y., Chatterjee, K., Doyen, L., Henzinger, T.A., Rabinovich, A.M., Raskin, J.F.: The complexity of multi-mean-payoff and multi-energy games. Inf. Comput. 241, 177–196 (2015). https://doi.org/10.1016/J.IC.2015.03.001

    2015 doi

  42. [52]

    Theoretical Computer Science200(1), 135–183 (1998)

    Zielonka, W.: Infinite games on finitely coloured graphs with applications to au- tomata on infinite trees. Theoretical Computer Science200(1), 135–183 (1998). https://doi.org/https://doi.org/10.1016/S0304-3975(98)00009-7

    1998 doi

  43. [442]

    https://doi.org/10.1007/11539452_33

    Springer (2005). https://doi.org/10.1007/11539452_33

    2005 doi

  44. [4127]

    https://doi.org/10.24963/IJCAI.2020/570

    ijcai.org (2020). https://doi.org/10.24963/IJCAI.2020/570

    2020 doi

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.