Pith. sign in

REVIEW 2 major objections 5 minor 269 references

Algorithms for Equilibria in Concurrent Stopping Games

T0 review · 2 major / 5 minor · reviewed 2026-07-31 · grok-4.5

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

Pith's one-line read In concurrent stopping games, approximate Nash equilibria are decidable in exponential time and extreme risk-sensitive equilibria are NP-complete.

desk verdict First unrestricted-strategy EXPTIME approx-NE algorithm for concurrent stopping games, plus NP-completeness for XRSE; two erratum-level slips in the truncation chain do not kill the theorems. read the letter →

arxiv 2607.24219 v1 pith:NXCTDIVV submitted 2026-07-27 cs.GT cs.MA

Léonard Brice , Thomas A. Henzinger , K. S. Thejaswini This is my paper · ORCID
classification cs.GTcs.MA MSC 91A1568Q2591A43
keywords Nashequilibriaconcurrentgamesstoppingε-Nashextremerisk-sensitiveconstrainedexistencemulti-agentsystems
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

The constrained existence problem for exact Nash equilibria is undecidable even in concurrent stopping games. This paper restores tractability in two ways. First, it decides whether an ε-Nash equilibrium with prescribed payoffs exists, running in time exponential in the game and only polynomial in the bit-size of ε, and proves the problem is already PSPACE-hard for turn-based games. Second, it shows that when players instead optimise the best or worst payoff that occurs with positive probability (extreme risk-sensitive equilibria), the same constrained existence question becomes NP-complete. Both results matter because they give the first algorithms that work for unrestricted strategies in the concurrent setting, a natural model of synchronous multi-agent systems that must eventually terminate.

What carries the argument

Characteristic vectors of finite-memory-horizon strategy profiles, discretised into cubes whose size is controlled by ε, together with an anchoring/rank labelling that produces a polynomial-size memory structure for XRSE witnesses.

What would settle it

Exhibit a concurrent stopping game and a rational ε for which the cube-over-approximation algorithm returns the wrong yes/no answer, or a polynomial-memory XRSE witness that the NP procedure rejects.

Watch

Extended reading notes

Core claim

For concurrent stopping games the approximate constrained-existence problem for Nash equilibria is in EXPTIME (and PSPACE-hard already for turn-based and pure equilibria), while the exact constrained-existence problem for extreme risk-sensitive equilibria is NP-complete.

Load-bearing premise

Every strategy profile must reach a terminal state with probability one; without that stopping assumption both the finite-horizon truncation and the rank construction fail.

Editorial extensions

If this is right

  • Exact Nash constrained existence stays undecidable, but any practical query that tolerates a known additive error becomes algorithmically answerable.
  • XRSE constrained existence can be decided by a nondeterministic polynomial-time guess of a polynomial-size memory structure followed by ordinary MDP reachability checks.
  • The same PSPACE lower bound applies to pure approximate equilibria, so randomisation is not the sole source of hardness.
  • Memoryless team-punishment strategies without shared randomness suffice to enforce XRSE deviations in the concurrent setting.

Reading between the lines

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

  • The exponential dependence on game size (via the horizon K) suggests that practical implementations will need aggressive pruning or symbolic representations of the cube sets.
  • Value-at-risk equilibria with a positive tolerance parameter look like a natural next target: the paper’s rank technique may lift once the support condition is replaced by a probability threshold.
  • If the stopping hypothesis can be relaxed to almost-sure termination under the candidate equilibrium alone, both algorithms would immediately apply to a larger class of concurrent games.
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

2 major / 5 minor

Summary. The paper studies the constrained existence problem for equilibria in terminal-reward concurrent stochastic games under the stopping assumption (every strategy profile reaches a terminal almost surely). Since the exact problem is undecidable even in this setting, the authors pursue two relaxations. First, they give an approximate (gap) decision procedure for constrained existence of Nash equilibria: they show that any NE can be truncated to an ε/2-NE of finite memory horizon KN (Lemmas 4–6), define a characteristic vector recording each player's payoff and best deviation value (Definition 8), and compute an inductive cube over-approximation of the set of characteristic vectors of horizon-k profiles with controlled error (Lemmas 10–11), yielding an algorithm that runs in time exponential in the game size and polynomial in the bit-size of ε (Theorem 12), plus a PSPACE-hardness lower bound via QBF (Theorem 14). Second, for extreme risk-sensitive equilibria (XRSE), they prove the constrained existence problem is NP-complete on concurrent stopping games (Theorem 29), via a finite-memory witness construction based on anchored players, i-ranks, and a combinatorial bound on the number of anchored sets (Lemmas 20–28).

Significance. If the results hold, this is a solid contribution. The approximate algorithm is the first for constrained NE existence without any restriction on strategies, and it quantifies the gain precisely: undecidability collapses to EXPTIME, with only polynomial dependence on the bit-size of epsilon — a sharp statement of what approximation buys. The PSPACE lower bound, already for turn-based pure equilibria, usefully delimits the gap. The XRSE half closes an explicitly open problem and the anchored-set counting argument (Lemma 22), which charges the potential exponential blow-up in anchored sets against the exponential input representation of concurrent transition matrices, is an elegant and genuinely concurrent-specific insight; the handling of uncorrelated punishment via [7] addresses a real obstacle rather than assuming it away. The stopping-games restriction is a real scope boundary but is stated honestly and motivated. The work is reproducible in the sense that all constructions are explicit and the complexity accounting is checkable; there are no hidden parameters.

major comments (2)
  1. [§3.5 and Theorem 12 (§3.6)] Discretisation parameter mismatch. The algorithm iterates "k ranging from 0 to KN" (correct, since Lemma 6 delivers memory horizon KN), and Lemma 10 bounds the approximation error of X_k by (k+1)R/D. At k = KN the error is (KN+1)R/D, but D is fixed as 2(K+1)R/epsilon, giving an error of roughly N*epsilon/2, which exceeds the epsilon/2 slack used in the soundness direction ("yes => positive instance") for every N >= 2. The fix is immediate: set D := 2(KN+1)R/epsilon. This does not affect the complexity claim, since D is already exponential in |G| and polynomial in the bit-size of epsilon. Relatedly, the complexity paragraph says "the maximal number of steps of this algorithm is K", which should read KN+1; the text oscillates between the two and should be made consistent.
  2. [Lemma 6, proof in Appendix A.1] The truncation construction has two defects. First, sigma-bar' is defined to follow sigma-bar for kN steps and is then defined "arbitrarily" on extensions of length-kN histories; but Definition 5 requires the continuation after the horizon to be memoryless, so an arbitrary continuation does not in general produce a profile of memory horizon kN. Second, the proof asserts "each player i has the same expected payoff as in sigma-bar" (and uses E(sigma-bar) = E(sigma-bar') in the final line), which the construction cannot guarantee. The adjacent citation of [14, Thm 3.2] for an exactly payoff-equivalent memoryless profile is immediately disavowed ("might not [be] possible without correlated strategies"), so that step is currently unsupported. The lemma's statement (payoffs within delta/2) is nevertheless true under a corrected argument: after kN steps, switch to any fixed memoryless profile;
minor comments (5)
  1. [Theorem 29 (§4.6) and Proposition 35 (App. B.3)] In the NP-membership argument, the guessed witness includes choice functions valued in probability distributions. The paper should state explicitly that a witness with polynomially bounded bit-size exists. This follows because all verification questions reduce to positive-probability and almost-sure reachability, which depend only on supports, not on probability values; a sentence making this explicit would close the gap. Similarly, in Proposition 35 the invocation of Lemma 27 requires the opponent profile to be memoryless; strictly, one must pass to the product of the game with the (polynomial-size) memory structure, on which sigma-bar*-_{-i} is memoryless. Worth one clarifying sentence.
  2. [Theorem 14, proof in App. A.4] The QBF instance is described with "each clause C_i is a conjunction of three literals"; this should be disjunction (the game construction and the rest of the argument are consistent with CNF clauses).
  3. [Lemma 4 proof (§3.2)] "the path can be chosen of length at most N+1" and later "from any path v" — the latter should read "from any vertex v". Also footnote 1 ("the number of action interactions is then kN") is cryptic; the convention that a step is a vertex visit while the horizon is measured in kN should be stated once, clearly, in the preliminaries.
  4. [Various] Typos and glitches: "problem of approximate constrained existence problem" (abstract and §3.1); "the can be done" (Thm 12 complexity paragraph); "doe snot" and "sine the vertex" (App. A.4); "Throught the claim" (App. B.3); "an delta-NE" (App. A.1); "from the result from the result from MDP literature" (§4.5); in Definition 5 the quantified memoryless profile is written tau-bar without the subscript h; "can be assume to form a punishing coalition" (§1).
  5. [Figures 1 and 2] Figures 1 and 2 are essential to following Example 17 and the QBF reduction, but the extracted/printed quality of the player glyphs and edge labels is poor; please check the final typeset versions for legibility.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: complexity upper/lower bounds derived from first-principles constructions plus independent black-box lemmas; self-citations are tools, not definitional restatements of the claims.

full rationale

This is a pure algorithms/complexity paper. Theorem 12 builds an EXPTIME decision procedure from three explicit steps (finite-horizon truncation of NEs, characteristic vectors, cube over-approximation via ETR), all developed in-section from stopping-probability bounds and discretisation; nothing is fitted to data or defined in terms of the target decision. Theorem 29’s NP upper bound is a new polynomial-memory XRSE construction (anchoring/ranks, memory structure); hardness is inherited from the turn-based special case [8], which is a legitimate subclass reduction, not a self-definition. The only author-overlapping citations ([7] for uncorrelated memoryless team punishment; [8] for XRSE definition and TB hardness) supply independent algorithmic lemmas used as black boxes; their statements do not include the concurrent constrained-existence claims being proved. No fitted-input-as-prediction, no uniqueness-imported-to-force-the-result, no renaming of a known empirical pattern. Proof slips noted by the skeptic (D vs KN mismatch; Lemma 6 payoff wording) are correctness/erratum issues, not circular reductions. Score 0 is the honest finding.

Assumptions & free parameters 0 free parameters · 6 assumptions · 3 invented entities

Load-bearing background is standard stochastic-game and complexity machinery plus two recent author results on XRSE and uncorrelated team punishment. No fitted numeric parameters. The stopping-game hypothesis and the promise formulation of the approximate problem are the main domain assumptions.

assumptions (6)
  • domain assumption Constrained NE existence is undecidable already for 10-player stopping games (Ummels–Wojtczak).
    Cited as Theorem 3 / [25]; motivates both relaxations.
  • standard math Existential theory of the reals is decidable in PSPACE (Canny).
    Used in Lemma 11 to decide cube membership when building X_k.
  • domain assumption In concurrent games, a coalition without shared randomness has memoryless strategies realizing almost-sure / positive-probability reachability values against one opponent ([7]).
    Lemma 26; essential for polynomial-memory XRSE punishment under concurrency.
  • standard math Against a memoryless opponent profile, a single player has an optimal positional strategy for extreme risk measures.
    Lemma 27; standard MDP fact used in the XRSE deviation check.
  • ad hoc to paper The input instance of the approximate problem is promised to be either a yes-instance for exact NE or a no-instance even for ε-NE with relaxed bounds.
    Problem 2 formulation; without the promise the algorithm only semi-decides a gap version.
  • domain assumption The game is stopping: every strategy profile reaches T with probability 1.
    Global hypothesis; powers Lemma 4 and the XRSE rank finiteness argument.
invented entities (3)
  • Characteristic vector of a strategy profile (reg/dev coordinates)
    purpose: Finite-dimensional summary sufficient to certify ε-NE and payoff constraints
    Definition 8; standard idea, packaged specifically for the cube iteration
  • Memory-horizon-k strategy profiles and the cube sequence X_k
    purpose: Discretized over-approximation enabling EXPTIME search
    Definitions 5 and 9; algorithmic devices, not physical entities
  • Anchorable players, i-rank, and anchored-set labelling Λ
    purpose: Extract a polynomial-size memory structure from an arbitrary XRSE
    Definitions 18–19, Lemma 21; proof devices for the NP upper bound

how reviews work

0 comments
Cite this review

Pith. "Pith review of Algorithms for Equilibria in Concurrent Stopping Games." pith.science (2026). https://pith.science/paper/NXCTDIVV

@misc{pith2026260724219,
  author       = {Pith},
  title        = {Pith review of: Algorithms for Equilibria in Concurrent Stopping Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NXCTDIVV}},
  note         = {Machine review of arXiv:2607.24219}
}
abstract

Concurrent games are a standard model for multi-agent systems, with Nash equilibrium as their central solution concept. The associated \emph{constrained existence problem}---does a game admit a Nash equilibrium whose expected payoff lies within a prescribed interval for every player?---is undecidable, and remains so even for 10-player \emph{stopping} games, in which a terminal state is reached almost surely under every strategy profile. We give two routes to tractability. We first relax exactness and consider the problem of approximate constrained existence problem, parametrised by $\varepsilon$-NE, which decides whether an \(\varepsilon\)-Nash equilibrium with the prescribed payoffs exists. The algorithm runs in exponential time, and only polynomially in the bit-size of \(\varepsilon\). We complement it with a \PSPACE-hardness lower bound that holds already for turn-based games, and for pure equilibria as well. We then relax the solution concept, turning to \emph{extreme risk-sensitive equilibria} (XRSE), recently introduced for turn-based stochastic games. Here the players are partitioned into optimists and pessimists, who evaluate a strategy profile by the best, respectively the worst, payoff attainable with positive probability, instead of the expected payoff. We prove that the constrained existence problem for XRSE is \NP-complete on concurrent games, as for turn-based games.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

269 extracted references · 5 canonical work pages

  1. [7]

    2024 , volume =

    Asadi, Ali and Chatterjee, Krishnendu and Saona, Raimundo and Svoboda, Jakub , title =. 2024 , volume =

    2024

  2. [1]

    2008 , publisher=

    Modern actuarial risk theory , author=. 2008 , publisher=

    2008

  3. [2]

    Randomise Alone, Reach as a Team , booktitle =

    L. Randomise Alone, Reach as a Team , booktitle =. 2026 , address =

    2026

  4. [3]

    and Kupferman, Orna , title =

    Alur, Rajeev and Henzinger, Thomas A. and Kupferman, Orna , title =. J. ACM , month = sep, pages =. 2002 , issue_date =. doi:10.1145/585265.585270 , abstract =

    arXiv 2002

  5. [4]

    Notes on Risk-Sensitive Nash Equilibria

    Nowak, Andrzej S. Notes on Risk-Sensitive Nash Equilibria. Advances in Dynamic Games: Applications to Economics, Finance, Optimization, and Stochastic Control. 2005. doi:10.1007/0-8176-4429-6_5

    doi:10.1007/0-8176-4429-6_5 2005

  6. [5]

    and Papadimitriou, Christos H

    Daskalakis, Constantinos and Goldberg, Paul W. and Papadimitriou, Christos H. , title =. SIAM Journal on Computing , volume =. 2009 , doi =

    2009

  7. [6]

    2024 , isbn =

    Bose, Sougata and Ibsen-Jensen, Rasmus and Totzke, Patrick , title =. 2024 , isbn =. doi:10.1145/3661814.3662096 , booktitle =

    arXiv 2024

  8. [8]

    Spirakis , editor =

    Argyrios Deligkas and John Fearnley and Themistoklis Melissourgos and Paul G. Spirakis , editor =. Approximating the Existential Theory of the Reals , booktitle =. 2018 , url =. doi:10.1007/978-3-030-04612-5\_9 , timestamp =

    work page doi:10.1007/978-3-030-04612-5 2018

Show all 269 references
  1. [9]

    Lipton and Evangelos Markakis and Aranyak Mehta , editor =

    Richard J. Lipton and Evangelos Markakis and Aranyak Mehta , editor =. Playing large games using simple strategies , booktitle =. 2003 , url =. doi:10.1145/779928.779933 , timestamp =

    2003

  2. [10]

    45th International Symposium on Mathematical Foundations of Computer Science,

    Kristoffer Arnsfelt Hansen and Steffan Christ S. 45th International Symposium on Mathematical Foundations of Computer Science,. 2020 , url =

    2020

  3. [11]

    Decision Theory: A Formal Philosophical Introduction

    Bradley, Richard. Decision Theory: A Formal Philosophical Introduction. Introduction to Formal Philosophy. 2018. doi:10.1007/978-3-319-77434-3_34

    2018 doi

  4. [12]

    2016 , edition =

    Stochastic Finance: An Introduction in Discrete Time , author =. 2016 , edition =

    2016

  5. [13]

    1950 , address =

    Abraham Wald , title =. 1950 , address =

    1950

  6. [14]

    Cowles Commission Discussion Paper: Statistics , year =

    Leonid Hurwicz , title =. Cowles Commission Discussion Paper: Statistics , year =

  7. [15]

    2017 , note =

    Meet your expectations with guarantees: Beyond worst-case synthesis in quantitative games , journal =. 2017 , note =. doi:https://doi.org/10.1016/j.ic.2016.10.011 , author =

    2017 doi

  8. [16]

    2023 , url =

    H2 Gambling Capital , title =. 2023 , url =

    2023

  9. [17]

    Howard and James E

    Ronald A. Howard and James E. Matheson , journal =. Risk-Sensitive Markov Decision Processes , urldate =

  10. [18]

    Progress Measures and Finite Arguments for Infinite Computations , author =

  11. [19]

    Richard , title =

    Büchi, J. Richard , title =. International Congress on Logic, Methodology, and Philosophy of Science , publisher =. 1962 , pages =

    1962

  12. [20]

    Number of Quantifiers is Better Than Number of Tape Cells , author=. J. Comput. Syst. Sci. , year=

  13. [21]

    Introduction to transcendental numbers

    Lang, Serge. Introduction to transcendental numbers. 1966

    1966

  14. [22]

    2010 , month = jan, school =

    Ummels, Michael , title =. 2010 , month = jan, school =

    2010

  15. [23]

    and Wilkie, Alex , year =

    Macintyre, A. and Wilkie, Alex , year =

  16. [24]

    Martin , journal =

    Donald A. Martin , journal =. Borel Determinacy , urldate =

  17. [25]

    Vardi , title =

    Moshe Y. Vardi , title =. Chic. J. Theor. Comput. Sci. , volume =. 1996 , url =

    1996

  18. [26]

    Souza and K

    Antonio Casares and Marcin Pilipczuk and Michał Pilipczuk and Uéverton S. Souza and K. S. Thejaswini , title =. 2023 , note =

    2023

  19. [28]

    The complexity of temporal constraint satisfaction problems , journal =

    Manuel Bodirsky and Jan K. The complexity of temporal constraint satisfaction problems , journal =. 2010 , url =. doi:10.1145/1667053.1667058 , timestamp =

    2010

  20. [29]

    John Fearnley and Rahul Savani , title =. Log. Methods Comput. Sci. , volume =. 2018 , url =. doi:10.23638/LMCS-14(4:9)2018 , timestamp =

    2018 doi

  21. [30]

    1972 , url =

    Robert Endre Tarjan , title =. 1972 , url =. doi:10.1137/0201010 , timestamp =

    1972 doi

  22. [31]

    Efficient Parallel Strategy Improvement for Parity Games , booktitle =

    John Fearnley , editor =. Efficient Parallel Strategy Improvement for Parity Games , booktitle =. 2017 , url =. doi:10.1007/978-3-319-63390-9\_8 , timestamp =

    2017 doi

  23. [32]

    On exact algorithms for the permutation

    Eun Jung Kim and Daniel Gon. On exact algorithms for the permutation. Theor. Comput. Sci. , volume =. 2013 , url =. doi:10.1016/j.tcs.2012.10.035 , timestamp =

    2013 doi

  24. [33]

    Russell Impagliazzo and Ramamohan Paturi and Francis Zane , title =. J. Comput. Syst. Sci. , volume =. 2001 , url =. doi:10.1006/jcss.2001.1774 , timestamp =

    2001

  25. [34]

    Alfred Tarski , journal =

  26. [35]

    Fomin and

    Marek Cygan and Fedor V. Fomin and. Parameterized Algorithms , publisher =. 2015 , url =

    2015

  27. [36]

    On Directed Feedback Vertex Set Parameterized by Treewidth , booktitle =

    Marthe Bonamy and. On Directed Feedback Vertex Set Parameterized by Treewidth , booktitle =. 2018 , url =. doi:10.1007/978-3-030-00256-5\_6 , timestamp =

    2018 doi

  28. [37]

    Solving Temporal

    Leif Eriksson , school =. Solving Temporal. 2019 , url =

    2019

  29. [38]

    Bodlaender and Fedor V

    Hans L. Bodlaender and Fedor V. Fomin and Arie M. C. A. Koster and Dieter Kratsch and Dimitrios M. Thilikos , title =. Theory Comput. Syst. , volume =. 2012 , url =. doi:10.1007/s00224-011-9312-0 , timestamp =

    2012 doi

  30. [39]

    Good-Enough Synthesis , booktitle =

    Shaull Almagor and Orna Kupferman , editor =. Good-Enough Synthesis , booktitle =. 2020 , url =. doi:10.1007/978-3-030-53291-8\_28 , timestamp =

    2020 doi

  31. [40]

    Henzinger and Barbara Jobstmann , editor =

    Krishnendu Chatterjee and Thomas A. Henzinger and Barbara Jobstmann , editor =. Environment Assumptions for Synthesis , booktitle =. 2008 , url =. doi:10.1007/978-3-540-85361-9\_14 , timestamp =

    2008 doi

  32. [41]

    Rational Synthesis , booktitle =

    Dana Fisman and Orna Kupferman and Yoad Lustig , editor =. Rational Synthesis , booktitle =. 2010 , url =. doi:10.1007/978-3-642-12002-2\_16 , timestamp =

    2010 doi

  33. [42]

    Vardi and Mihalis Yannakakis , editor =

    Orna Kupferman and Yoad Lustig and Moshe Y. Vardi and Mihalis Yannakakis , editor =. Temporal Synthesis for Bounded Systems and Environments , booktitle =. 2011 , url =. doi:10.4230/LIPIcs.STACS.2011.615 , timestamp =

    2011 doi

  34. [43]

    Vardi , editor =

    Orna Kupferman and Giuseppe Perelli and Moshe Y. Vardi , editor =. Synthesis with Rational Environments , booktitle =. 2014 , url =. doi:10.1007/978-3-319-17130-2\_15 , timestamp =

    2014 doi

  35. [44]

    Vardi , title =

    Orna Kupferman and Giuseppe Perelli and Moshe Y. Vardi , title =. Ann. Math. Artif. Intell. , volume =. 2016 , url =. doi:10.1007/s10472-016-9508-8 , timestamp =

    2016 doi

  36. [45]

    Ali Asadi and L. 45th. 2025 , url =

    2025

  37. [46]

    Allen Emerson and Charanjit S

    E. Allen Emerson and Charanjit S. Jutla , title =. 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988 , pages =. 1988 , url =. doi:10.1109/SFCS.1988.21949 , timestamp =

    1988

  38. [47]

    Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages , pages =

    Francez, Nissim and Kozen, Dexter , title =. Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages , pages =. 1984 , isbn =. doi:10.1145/800017.800515 , abstract =

    1984

  39. [48]

    Henzinger , editor =

    Krishnendu Chatterjee and Luca de Alfaro and Thomas A. Henzinger , editor =. The Complexity of Stochastic. Automata, Languages and Programming, 32nd International Colloquium,. 2005 , url =. doi:10.1007/11523468\_71 , timestamp =

    2005 doi

  40. [49]

    CoRR , volume =

    Richard Combes and Mikael Touati , title =. CoRR , volume =. 2020 , url =. 2007.08387 , timestamp =

    2020 arXiv

  41. [50]

    Universal Graphs and Good for Games Automata: New Tools for Infinite Duration Games

    Colcombet, Thomas and Fijalkow, Nathana \"e l. Universal Graphs and Good for Games Automata: New Tools for Infinite Duration Games. Foundations of Software Science and Computation Structures. 2019

    2019

  42. [51]

    Solving Odd-Fair Parity Games , booktitle =

    Irmak Saglam and Anne. Solving Odd-Fair Parity Games , booktitle =. 2023 , url =. doi:10.4230/LIPICS.FSTTCS.2023.34 , timestamp =

    2023 doi

  43. [52]

    Solving Two-Player Games Under Progress Assumptions , booktitle =

    Anne. Solving Two-Player Games Under Progress Assumptions , booktitle =. 2024 , url =. doi:10.1007/978-3-031-50524-9\_10 , timestamp =

    2024 doi

  44. [53]

    Souza and K

    Antonio Casares and Marcin Pilipczuk and Michał Pilipczuk and Uéverton S. Souza and K. S. Thejaswini , title =. Symposium on Simplicity in Algorithms (SOSA) , chapter =. 2024 , doi =

    2024

  45. [54]

    Henzinger and Nir Piterman , editor =

    Krishnendu Chatterjee and Thomas A. Henzinger and Nir Piterman , editor =. Generalized Parity Games , booktitle =. 2007 , url =. doi:10.1007/978-3-540-71389-0\_12 , timestamp =

    2007 doi

  46. [55]

    Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games , booktitle =

    Nathana. Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games , booktitle =. 2020 , url =. doi:10.4230/LIPIcs.MFCS.2020.34 , timestamp =

    2020 doi

  47. [56]

    Henzinger and Marcin Jurdzi\'

    Krishnendu Chatterjee and Thomas A. Henzinger and Marcin Jurdzi\'. Mean-Payoff Parity Games , booktitle =. 2005 , url =. doi:10.1109/LICS.2005.26 , timestamp =

    2005 doi

  48. [57]

    2008 , url =

    Yde Venema , title =. 2008 , url =

    2008

  49. [58]

    and K\"onig, B

    Baldan, P. and K\"onig, B. and Mika-Michalski, C. and Padoan, T. , title =. Proceedings of the ACM on Programming Languages , year =

  50. [60]

    Maciej Gazda and Tim A. C. Willemse , editor =. Zielonka's Recursive Algorithm: dull, weak and solitaire games and tighter bounds , booktitle =. 2013 , url =. doi:10.4204/EPTCS.119.4 , timestamp =

    2013 doi

  51. [61]

    Burch, J. R. and Clarke, E. M. and McMillan, K. L. and Dill, D. L. and Hwang, L. J. , title =. Inf. Comput. , year =

  52. [62]

    and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank , title =

    Calude, Cristian S. and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank , title =. SIAM Journal on Computing , volume =. 2022 , doi =

    2022

  53. [63]

    Calude, C. S. and Jain, S. and Khoussainov, B. and Li, W. and Stephan, F. , title =. STOC 2017 , year =

    2017

  54. [64]

    SIAM Journal on Computing , volume =

    Tarjan, Robert , title =. SIAM Journal on Computing , volume =. 1972 , doi =

    1972

  55. [65]

    Monotonic graphs for Parity and Mean-Payoff games , author =

  56. [66]

    K. S. Thejaswini and Pierre Ohlmann and Marcin Jurdzinski , editor =. A Technique to Speed up Symmetric Attractor-Based Algorithms for Parity Games , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.FSTTCS.2022.44 , timestamp =

    2022 doi

  57. [67]

    K. S. Thejaswini. Parity Games and Register Index. 2019

    2019

  58. [68]

    , title =

    Luca de Alfaro and Henzinger, Thomas A. , title =. Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science , pages =. 2000 , isbn =

    2000

  59. [69]

    Proceedings of the National Academy of Sciences , year=

    Stochastic Games* , author=. Proceedings of the National Academy of Sciences , year=

  60. [70]

    Vardi , editor =

    Valerie King and Orna Kupferman and Moshe Y. Vardi , editor =. On the Complexity of Parity Word Automata , booktitle =. 2001 , url =. doi:10.1007/3-540-45315-6\_18 , timestamp =

    2001 doi

  61. [71]

    Rabin Games and Colourful Universal Trees , year =

    Rupak Majumdar and Irmak Sa. Rabin Games and Colourful Universal Trees , year =

  62. [72]

    Rabinizer 4: From LTL to Your Favourite Deterministic Automaton

    K r et \'i nsk \'y , Jan and Meggendorfer, Tobias and Sickert, Salomon and Ziegler, Christopher. Rabinizer 4: From LTL to Your Favourite Deterministic Automaton. Computer Aided Verification. 2018

    2018

  63. [73]

    and Dawar, A

    Berwanger, D. and Dawar, A. and Hunter, P. and Kreutzer, S. , title =. STACS , pages =. 2006 , url =. doi:, timestamp =

    2006

  64. [74]

    Fast Mu-Calculus Model Checking when Tree-Width Is Bounded , booktitle =

    Obdrz. Fast Mu-Calculus Model Checking when Tree-Width Is Bounded , booktitle =. 2003 , url =. doi:, timestamp =

    2003

  65. [75]

    Konrad Staniszewski , title =. 31st. 2023 , doi =

    2023

  66. [76]

    An Accelerated Algorithm for 3-Color Parity Games with an Application to Timed Games

    de Alfaro, Luca and Faella, Marco. An Accelerated Algorithm for 3-Color Parity Games with an Application to Timed Games. Computer Aided Verification. 2007

    2007

  67. [77]

    A short proof of correctness of the quasi-polynomial time algorithm for parity games , journal =

    Hugo Gimbert and Rasmus Ibsen. A short proof of correctness of the quasi-polynomial time algorithm for parity games , journal =. 2017 , url =. 1702.01953 , timestamp =

    2017 arXiv

  68. [78]

    Parity Games of Bounded Tree- and Clique-Width

    Ganardi, Moses. Parity Games of Bounded Tree- and Clique-Width. Foundations of Software Science and Computation Structures. 2015

    2015

  69. [79]

    Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science , articleno =

    Ohlmann, Pierre , title =. Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science , articleno =. 2022 , isbn =. doi:10.1145/3531130.3532418 , abstract =

    2022

  70. [80]

    Slightly Superexponential Parameterized Problems , journal =

    Lokshtanov, Daniel and Marx, D\'. Slightly Superexponential Parameterized Problems , journal =. 2018 , doi =

    2018

  71. [81]

    30th International Symposium on Mathematical Foundations of Computer Science,

    Paul Hunter and Anuj Dawar , title =. 30th International Symposium on Mathematical Foundations of Computer Science,. 2005 , url =. doi:10.1007/11549345\_43 , timestamp =

    2005 doi

  72. [82]

    Parity Games on Graphs with Medium Tree-Width

    Fearnley, John and Lachish, Oded. Parity Games on Graphs with Medium Tree-Width. Mathematical Foundations of Computer Science 2011. 2011

    2011

  73. [83]

    and Kreutzer, S

    Hunter, P. and Kreutzer, S. , title =. SODA , pages =. 2007 , url =

    2007

  74. [84]

    Clique-Width and Parity Games , booktitle =

    Obdrz. Clique-Width and Parity Games , booktitle =. 2007 , url =. doi:, timestamp =

    2007

  75. [85]

    Berwanger, D. and Gr. Entanglement -. LPAR , pages =. 2004 , url =. doi:, timestamp =

    2004

  76. [86]

    An Automata Toolbox , publisher =

    Boja. An Automata Toolbox , publisher =. 2017 , type =

    2017

  77. [87]

    Aditya Prakash and K. S. Thejaswini , editor =. On History-Deterministic One-Counter Nets , booktitle =. 2023 , url =. doi:10.1007/978-3-031-30829-1\_11 , timestamp =

    2023 doi

  78. [88]

    Balasubramanian, A. R. and Thejaswini, K. S. , title =. 32nd International Conference on Concurrency Theory (CONCUR 2021) , pages =. 2021 , volume =. doi:10.4230/LIPIcs.CONCUR.2021.17 , annote =

    2021 doi

  79. [89]

    Chatterjee, K. and Dvo. Quasipolynomial set-based symbolic algorithms for parity games , OPTcrossref =. LPAR-22 , year =

  80. [90]

    and Daviaud, L

    Czerwi\'nski, W. and Daviaud, L. and Fijalkow, N. and Jurdzi. Universal trees grow inside separating automata:. Proceedings of the Thirtieth Annual. 2019 , url =. doi:10.1137/1.9781611975482.142 , timestamp =

    2019 doi

  81. [92]

    and Jurdzi

    Daviaud, L. and Jurdzi. Alternating weak automata from universal trees , OPTcrossref =. 30th International Conference on Concurrency Theory, CONCUR 2019 , year =

    2019

  82. [93]

    Massimo Benerecetti and Daniele Dell'Erba and Fabio Mogavero , title =. Inf. Comput. , volume =. 2020 , url =. doi:10.1016/j.ic.2019.104501 , timestamp =

    2020

  83. [94]

    Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees , booktitle =

    Zhuan Khye Koh and Georg Loho , editor =. Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.MFCS.2022.63 , timestamp =

    2022 doi

  84. [95]

    Laure Daviaud and Marcin Jurdzi. The. 47th International Colloquium on Automata, Languages, and Programming,. 2020 , url =. doi:10.4230/LIPIcs.ICALP.2020.123 , timestamp =

    2020 doi

  85. [96]

    Allen Emerson and Charanjit S

    E. Allen Emerson and Charanjit S. Jutla , title =. 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991 , pages =. 1991 , url =. doi:10.1109/SFCS.1991.185392 , timestamp =

    1991

  86. [97]

    Allen Emerson and Charanjit S

    E. Allen Emerson and Charanjit S. Jutla and A. Prasad Sistla , editor =. On Model-Checking for Fragments of. Computer Aided Verification, 5th International Conference,. 1993 , url =. doi:10.1007/3-540-56922-7\_32 , timestamp =

    1993 doi

  87. [98]

    Ershov, A. P. , title =. Communications of the ACM , year =

  88. [99]

    Schuller , title =

    Kousha Etessami and Thomas Wilke and Rebecca A. Schuller , title =. Automata, Languages and Programming, 28th International Colloquium,. 2001 , url =. doi:10.1007/3-540-48224-5\_57 , timestamp =

    2001 doi

  89. [100]

    , title =

    Fearnley, J. , title =. ICALP 2010 , year =

    2010

  90. [101]

    and Jain, S

    Fearnley, J. and Jain, S. and de Keijzer, B. and Schewe, S. and Stephan, F. and Wojtczak, D. , title =. International Journal on Software Tools for Technology Transfer , year =

  91. [102]

    , title =

    Friedmann, O. , title =. LICS 2009 , year =

    2009

  92. [103]

    , title =

    Friedmann, O. , title =. IPCO 2011 , year =

    2011

  93. [104]

    2011 , url =

    Oliver Friedmann , title =. 2011 , url =. doi:10.1051/ita/2011124 , timestamp =

    2011

  94. [105]

    and Hansen, T

    Friedmann, O. and Hansen, T. D. and Zwick, U. , title =. STOC 2011 , year =

    2011

  95. [106]

    2002 , url =

    Automata, Logics, and Infinite Games:. 2002 , url =. doi:10.1007/3-540-36387-4 , isbn =

    2002 doi

  96. [107]

    Dependable Software Systems Engineering , year=

    Synthesis of Reactive Systems , author=. Dependable Software Systems Engineering , year=

  97. [108]

    Richard and Landweber, Lawrence H

    Buchi, J. Richard and Landweber, Lawrence H. , year=. Definability in the monadic second-order theory of successor , volume=. The Journal of Symbolic Logic , publisher=. doi:10.2307/2271090 , number=

    doi

  98. [109]

    and Saoudi, Ahmed and Schupp, Paul E

    Muller, David E. and Saoudi, Ahmed and Schupp, Paul E. Alternating automata, the weak monadic theory of the tree, and its complexity. Automata, Languages and Programming. 1986

    1986

  99. [110]

    Theoretical Computer Science , volume =

    Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of. Theoretical Computer Science , volume =. 1995 , issn =. doi:https://doi.org/10.1016/0304-3975(94)00214-4 , url =

    1995 doi

  100. [111]

    1997 , issn =

    Fixed point characterization of infinite behavior of finite-state systems , journal =. 1997 , issn =. doi:https://doi.org/10.1016/S0304-3975(97)00039-X , url =

    1997 doi

  101. [112]

    Allen and Halpern, Joseph Y

    Emerson, E. Allen and Halpern, Joseph Y. , title =. J. ACM , month =. 1986 , issue_date =. doi:10.1145/4904.4999 , abstract =

    1986

  102. [113]

    Allen Emerson and Joseph Y

    E. Allen Emerson and Joseph Y. Halpern , title =. J. Comput. Syst. Sci. , volume =. 1985 , url =. doi:10.1016/0022-0000(85)90001-7 , timestamp =

    1985 doi

  103. [114]

    Clarke and E

    Edmund M. Clarke and E. Allen Emerson , editor =. Design and Synthesis of Synchronization Skeletons Using Branching-Time Temporal Logic , booktitle =. 1981 , url =. doi:10.1007/BFb0025774 , timestamp =

    1981 doi

  104. [115]

    Bradfield, J. C. On the expressivity of the modal mu-calculus. STACS 96. 1996

    1996

  105. [116]

    Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

    Daskalakis, Constantinos and Papadimitriou, Christos , title =. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2011 , publisher =

    2011

  106. [117]

    and Hollender, Alexandros and Savani, Rahul , title =

    Fearnley, John and Goldberg, Paul W. and Hollender, Alexandros and Savani, Rahul , title =. 2021 , isbn =. doi:10.1145/3406325.3451052 , booktitle =

    2021

  107. [118]

    Proceedings of the Third Annual Symposium on Logic in Computer Science

    Damian Niwi\'nski , title =. Proceedings of the Third Annual Symposium on Logic in Computer Science. 1988 , url =. doi:10.1109/LICS.1988.5137 , timestamp =

    1988

  108. [119]

    Stockmeyer, Larry Joseph , title =

  109. [120]

    Hennessy, Matthew and Milner, Robin , title =. J. ACM , month =. 1985 , issue_date =. doi:10.1145/2455.2460 , abstract =

    1985

  110. [121]

    EXPTIME Tableaux for the Coalgebraic -Calculus

    C \^i rstea, Corina and Kupke, Clemens and Pattinson, Dirk. EXPTIME Tableaux for the Coalgebraic -Calculus. Computer Science Logic. 2009

    2009

  111. [122]

    Gurvich and A.V

    V.A. Gurvich and A.V. Karzanov and L.G. Khachivan , abstract =. Cyclic games and an algorithm to find minimax cycle means in directed graphs , journal =. 1988 , issn =. doi:https://doi.org/10.1016/0041-5553(88)90012-2 , url =

    1988 doi

  112. [123]

    The Complexity of the Graded -Calculus

    Kupferman, Orna and Sattler, Ulrike and Vardi, Moshe Y. The Complexity of the Graded -Calculus. Automated Deduction---CADE-18. 2002

    2002

  113. [124]

    and Browne, Anca and Clarke, Edmund M

    Long, David E. and Browne, Anca and Clarke, Edmund M. and Jha, Somesh and Marrero, Wilfredo R. An improved algorithm for the evaluation of fixpoint expressions. Computer Aided Verification. 1994

    1994

  114. [125]

    Graph Games and Reactive Synthesis , booktitle =

    Roderick Bloem and Krishnendu Chatterjee and Barbara Jobstmann , editor =. Graph Games and Reactive Synthesis , booktitle =. 2018 , url =. doi:10.1007/978-3-319-10575-8\_27 , timestamp =

    2018 doi

  115. [126]

    Allen Emerson and Chin

    E. Allen Emerson and Chin. Efficient Model Checking in Fragments of the Propositional Mu-Calculus (Extended Abstract) , booktitle =. 1986 , timestamp =

    1986

  116. [127]

    Lattice-theoretic progress measures and coalgebraic model checking , booktitle =

    Ichiro Hasuo and Shunsuke Shimizu and Corina C. Lattice-theoretic progress measures and coalgebraic model checking , booktitle =. 2016 , url =. doi:10.1145/2837614.2837673 , timestamp =

    2016

  117. [128]

    , title =

    Jurdzi\'nski, M. , title =. 17th Annual Symposium on Theoretical Aspects of Computer Science , year =

  118. [129]

    and Lazi\'c, R

    Jurdzi\'nski, M. and Lazi\'c, R. , title =. 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017 , year =

    2017

  119. [130]

    Keiren, J. J. A. , title =. FSEN , year =

  120. [131]

    Knuth, D. E. , ALTeditor =. The Art of Computer Programming , publisher =. 1973 , OPTkey =

    1973

  121. [132]

    and Paterson, M

    Jurdzi\'nski, M. and Paterson, M. and Zwick, U. , title =. SIAM Journal on Computing , year =

  122. [133]

    , title =

    Lehtinen, K. , title =. 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 , year =

    2018

  123. [134]

    2020 , MONTH = May, KEYWORDS =

    Karoliina Lehtinen and Udi Boker , URL =. 2020 , MONTH = May, KEYWORDS =. doi:10.23638/LMCS-16(2:6)2020 , JOURNAL =

    2020 doi

  124. [135]

    and Schewe, S

    Lehtinen, K. and Schewe, S. and Wojtczak, D. , title =. 2019 , OPTnote =. 1904.11810 , OPTannote =

    2019 arXiv

  125. [136]

    and Meyer, P

    Luttenberger, M. and Meyer, P. J. and Sickert, S. , title =. 2019 , OPTnote =

    2019

  126. [137]

    , title =

    McNaughton, R. , title =. Annals of Pure and Applied Logic , year =

  127. [138]

    , title =

    Parys, P. , title =. MFCS 2019 , year =

    2019

  128. [139]

    , title =

    Parys, P. , title =. 28th EACSL Annual Conference on Computer Science Logic, CSL 2020 , year =

    2020

  129. [140]

    and P\'erez, G

    Jacobs, S. and P\'erez, G. A. and Bloem (Organizers), R. , title =. 2020 , note =

    2020

  130. [141]

    , title =

    van Dijk, T. , title =. Tools and Algorithms for the Construction and Analysis of Systems, 24th International Conference, TACAS 2018 , year =. doi:10.1007/978-3-319-89960-2\_16 , OPTnote =

    2018 doi

  131. [142]

    A Parity Game Tale of Two Counters , booktitle =

    Tom van Dijk , editor =. A Parity Game Tale of Two Counters , booktitle =. 2019 , url =. doi:10.4204/EPTCS.305.8 , timestamp =

    2019 doi

  132. [143]

    Viennot, X. G. , title =. 15th Colloquium on Trees in Algebra and Programming , year =

  133. [144]

    Proceedings of the 16th International Conference on Logic-Based Program Synthesis and Transformation , pages =

    Schewe, Sven and Finkbeiner, Bernd , title =. Proceedings of the 16th International Conference on Logic-Based Program Synthesis and Transformation , pages =. 2006 , isbn =

    2006

  134. [145]

    1995 , Month =

    Puri, Anuj , Title =. 1995 , Month =

    1995

  135. [146]

    , booktitle=

    Piterman, N. , booktitle=. From Nondeterministic Buchi and Streett Automata to Deterministic Parity Automata , year=

  136. [148]

    CoRR , volume =

    Massimo Benerecetti and Daniele Dell'Erba and Fabio Mogavero and Sven Schewe and Dominik Wojtczak , title =. CoRR , volume =. 2021 , url =. 2105.01738 , timestamp =

    2021 arXiv

  137. [149]

    CoRR , volume =

    Sven Schewe and Ashutosh Trivedi and Thomas Varghese , title =. CoRR , volume =. 2015 , url =. 1501.06484 , timestamp =

    2015 arXiv

  138. [150]

    2022 , MONTH = Jan, KEYWORDS =

    Karoliina Lehtinen and Paweł Parys and Sven Schewe and Dominik Wojtczak , URL =. 2022 , MONTH = Jan, KEYWORDS =. doi:10.46298/lmcs-18(1:8)2022 , JOURNAL =

    2022 doi

  139. [152]

    Bulletin of The Belgian Mathematical Society-simon Stevin , year=

    Alternating tree automata, parity games, and modal -calculus , author=. Bulletin of The Belgian Mathematical Society-simon Stevin , year=

  140. [153]

    1983 , note =

    Results on the propositional -calculus , journal =. 1983 , note =. doi:https://doi.org/10.1016/0304-3975(82)90125-6 , author =

    1983 doi

  141. [154]

    Streett and E

    Robert S. Streett and E. Allen Emerson , abstract =. An automata theoretic decision procedure for the propositional mu-calculus , journal =. 1989 , issn =. doi:https://doi.org/10.1016/0890-5401(89)90031-X , url =

    1989 doi

  142. [155]

    Mu-Calculus Model Checking

    McMillan, Kenneth L. Mu-Calculus Model Checking. Symbolic Model Checking. 1993. doi:10.1007/978-1-4615-3190-6_6

    1993 doi

  143. [156]

    Deciding the Winner in Parity Games is in

    Jurdzi\'. Deciding the Winner in Parity Games is in. 1998 , issue_date =. doi:10.1016/S0020-0190(98)00150-1 , journal =

    1998 doi

  144. [157]

    2013 , school=

    Practical improvements to parity game solving , author=. 2013 , school=

    2013

  145. [158]

    Formal Methods Syst

    Massimo Benerecetti and Daniele Dell'Erba and Fabio Mogavero , title =. Formal Methods Syst. Des. , volume =. 2018 , url =. doi:10.1007/s10703-018-0315-1 , timestamp =

    2018 doi

  146. [159]

    Verification, Model Checking, and Abstract Interpretation , year =

    Lapauw, Ruben and Bruynooghe, Maurice and Denecker, Marc , title =. Verification, Model Checking, and Abstract Interpretation , year =. doi:10.1007/978-3-030-39322-9_21 , pages =

    doi

  147. [160]

    and Kozen, D

    Klarlund, N. and Kozen, D. , booktitle=. Rabin measures and their applications to fairness and automata theory , year=

  148. [161]

    Solving Parity Games via Priority Promotion , booktitle =

    Massimo Benerecetti and Daniele Dell'Erba and Fabio Mogavero , editor =. Solving Parity Games via Priority Promotion , booktitle =. 2016 , url =. doi:10.1007/978-3-319-41540-6\_15 , timestamp =

    2016 doi

  149. [162]

    , title =

    Zielonka, W. , title =. Theoretical Computer Science , year =

  150. [163]

    Queille, J. P. and Sifakis, J. , title=. Acta Informatica , year=. doi:10.1007/BF00265555 , url=

    doi

  151. [164]

    Universal Algorithms for Parity Games and Nested Fixpoints , booktitle =

    Marcin Jurdzi. Universal Algorithms for Parity Games and Nested Fixpoints , booktitle =. 2022 , url =. doi:10.1007/978-3-031-22337-2\_12 , timestamp =

    2022 doi

  152. [165]

    A Direct Symbolic Algorithm for Solving Stochastic R abin Games

    Banerjee, Tamajit and Majumdar, Rupak and Mallik, Kaushik and Schmuck, Anne-Kathrin and Soudjani, Sadegh. A Direct Symbolic Algorithm for Solving Stochastic R abin Games. Tools and Algorithms for the Construction and Analysis of Systems. 2022

    2022

  153. [166]

    29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988 , pages =

    Shmuel Safra , title =. 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988 , pages =. 1988 , url =. doi:10.1109/SFCS.1988.21948 , timestamp =

    1988

  154. [167]

    Allen and Jutla, Charanjit S

    Emerson, E. Allen and Jutla, Charanjit S. , title =. SIAM Journal on Computing , volume =. 1999 , doi =

    1999

  155. [168]

    and Pnueli, A

    Piterman, N. and Pnueli, A. , booktitle=. Faster Solutions of. 2006 , volume=

    2006

  156. [169]

    Baier, Christel and Katoen, Joost-Pieter , biburl =

  157. [170]

    and Markey, N

    Bouyer, P. and Markey, N. and Olschewski, J. and Ummels, M. , title =. ATVA , year =

  158. [171]

    Summaries of the Summer Institute of Symbolic Logic , volume=

    Application of recursive arithmetic to the problem of circuit synthesis , author=. Summaries of the Summer Institute of Symbolic Logic , volume=

  159. [172]

    Rabin , journal =

    Michael O. Rabin , journal =. Decidability of Second-Order Theories and Automata on Infinite Trees , urldate =

  160. [173]

    , title =

    Streett, Robert S. , title =. Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing , pages =. 1981 , isbn =. doi:10.1145/800076.802492 , abstract =

    1981

  161. [174]

    and Rosner, R

    Pnueli, A. and Rosner, R. , title =. 1989 , isbn =. doi:10.1145/75277.75293 , booktitle =

    1989

  162. [175]

    The Theory of Universal Graphs for Infinite Duration Games , journal =

    Thomas Colcombet and Nathana. The Theory of Universal Graphs for Infinite Duration Games , journal =. 2022 , url =. doi:10.46298/lmcs-18(3:29)2022 , timestamp =

    2022 doi

  163. [176]

    and Gradel, Erich , title =

    Apt, Krzysztof R. and Gradel, Erich , title =. 2011 , isbn =

    2011

  164. [177]

    Games on Graphs , author =

  165. [178]

    Symposium on the Theory of Computing , year=

    Weak alternating automata and tree automata emptiness , author=. Symposium on the Theory of Computing , year=

  166. [179]

    A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games

    Bj \"o rklund, Henrik and Sandberg, Sven and Vorobyov, Sergei. A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games. Mathematical Foundations of Computer Science 2004. 2004

    2004

  167. [180]

    Distributed Synthesis for Alternating-Time Logics , booktitle =

    Sven Schewe and Bernd Finkbeiner , editor =. Distributed Synthesis for Alternating-Time Logics , booktitle =. 2007 , url =. doi:10.1007/978-3-540-75596-8\_20 , timestamp =

    2007 doi

  168. [181]

    An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games , booktitle =

    Sven Schewe , editor =. An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games , booktitle =. 2008 , url =. doi:10.1007/978-3-540-87531-4\_27 , timestamp =

    2008 doi

  169. [182]

    CoRR , volume =

    Michael Luttenberger , title =. CoRR , volume =. 2008 , url =. 0806.2923 , timestamp =

    2008 arXiv

  170. [183]

    Frontiers Comput

    Daniele Dell'Erba and Sven Schewe , title =. Frontiers Comput. Sci. , volume =. 2022 , url =. doi:10.3389/FCOMP.2022.936903 , timestamp =

    2022

  171. [184]

    1966 , issn =

    Testing and generating infinite sequences by a finite automaton , journal =. 1966 , issn =. doi:https://doi.org/10.1016/S0019-9958(66)80013-X , url =

    1966 doi

  172. [185]

    and Chaloupka, J

    Brim, L. and Chaloupka, J. and Doyen, L. and Gentilini, R. and Raskin, J.-F. , title =. Form. Methods Syst. Des. , year =

  173. [186]

    and Doyen, L

    Chatterjee, K. and Doyen, L. , title =. Theoretical Computer Science , year =

  174. [187]

    Games in Design and Verification , year=

    Streett games on finite graphs , author=. Games in Design and Verification , year=

  175. [188]

    and Doyen, L

    Chatterjee, K. and Doyen, L. and Gimbert, H. and Oualhadj, Y. , title =. FOSSACS , year =

  176. [189]

    and Henzinger, M

    Chatterjee, K. and Henzinger, M. and Svozil, A. , title =. MFCS , year =

  177. [190]

    and Rizzi, R

    Comin, C. and Rizzi, R. , title =. Algorithmica , year =

  178. [191]

    , title =

    Condon, A. , title =. Information and Computation , year =

  179. [192]

    and Mycielski, J

    Ehrenfeucht, A. and Mycielski, J. , title =. Journal of Game Theory , year =

  180. [193]

    Allen and Jutla, Charanjit and Sistla, Aravinda Prasad , title =

    Emerson, E. Allen and Jutla, Charanjit and Sistla, Aravinda Prasad , title =. Theoretical Computer Science , year =

  181. [194]

    and Jain, S

    Fearnley, J. and Jain, S. and Schewe, S. and Stephan, F. and Wojtczak, D. , title =. SPIN , year =

  182. [195]

    and Luttenberger, M

    Esparza, J. and Luttenberger, M. and Schlund, M. , title =. 2016 , OPTkey =

    2016

  183. [196]

    and Harrington, L

    Gurevich, Y. and Harrington, L. , title =. STOC , year =

  184. [197]

    Johnson, D. S. , title =. ACM Transactions on Algorithms , year =

  185. [198]

    18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977 , pages =

    Amir Pnueli , title =. 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977 , pages =. 1977 , url =. doi:10.1109/SFCS.1977.32 , timestamp =

    1977 doi

  186. [199]

    Roderick Bloem and Barbara Jobstmann and Nir Piterman and Amir Pnueli and Yaniv Sa'ar , title =. J. Comput. Syst. Sci. , volume =. 2012 , url =. doi:10.1016/j.jcss.2011.08.007 , timestamp =

    2012 doi

  187. [200]

    A. J. Hoffman and R. M. Karp , journal =. On Nonterminating Stochastic Games , urldate =

  188. [201]

    R. A. Howard , year=. Dynamic Programming and Markov Processes. Pp. 136. 46s. 1960. (John Wiley and Sons, N.Y.) , publisher=

    1960

  189. [202]

    and Kozen, D

    Klarlund, N. and Kozen, D. , title =. Chicago Journal of Theoretical Computer Science , year =

  190. [203]

    , title =

    Schewe, S. , title =. Journal of Computer and Systems Sciences , year =

  191. [204]

    , title =

    Thomas, W. , title =. STACS , year =

  192. [205]

    and Paterson, M

    Zwick, U. and Paterson, M. , title =. Theoretical Computer Science , year =

  193. [206]

    Oxford University Press google schola , volume=

    An Introduction to Game Theory , author=. Oxford University Press google schola , volume=

  194. [207]

    2020 , url=

    Multistage stochastic programs with the entropic risk measure , author=. 2020 , url=

    2020

  195. [208]

    CoRR , volume =

    Udi Boker and Karoliina Lehtinen , title =. CoRR , volume =. 2019 , url =

    2019

  196. [209]

    1991 , institution=

    Games with forbidden positions, University of Gdansk , author=. 1991 , institution=

    1991

  197. [210]

    , title =

    Chatterjee, Krishnendu and Alfaro, Luca de and Henzinger, Thomas A. , title =. 2011 , issue_date =. doi:10.1145/1970398.1970404 , journal =

    2011

  198. [211]

    Optimal Satisfiability Checking for Arithmetic

    Daniel Hausmann and Lutz Schr. Optimal Satisfiability Checking for Arithmetic. Foundations of Software Science and Computation Structures , year=

  199. [212]

    Quasipolynomial Computation of Nested Fixpoints , booktitle =

    Daniel Hausmann and Lutz Schr. Quasipolynomial Computation of Nested Fixpoints , booktitle =. 2021 , url =. doi:10.1007/978-3-030-72016-2\_3 , timestamp =

    2021 doi

  200. [213]

    Mathematical notes of the Academy of Sciences of the USSR , year=

    On minimal universal trees , author=. Mathematical notes of the Academy of Sciences of the USSR , year=

  201. [214]

    A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation , booktitle =

    Andr. A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation , booktitle =. 2021 , url =. doi:10.4230/LIPIcs.CSL.2021.9 , timestamp =

    2021 doi

  202. [215]

    A Multi-Core Solver for Parity Games , journal =

    Jaco. A Multi-Core Solver for Parity Games , journal =. 2008 , note =. doi:https://doi.org/10.1016/j.entcs.2008.11.011 , url =

    2008 doi

  203. [216]

    and Morvan, R

    Jurdzi\'nski, M. and Morvan, R. , title =. 2020 , OPTnote =

    2020

  204. [217]

    Strategy construction in infinite games with Streett and Rabin chain winning conditions

    Buhrke, Nils and Lescow, Helmut and V \"o ge, Jens. Strategy construction in infinite games with Streett and Rabin chain winning conditions. Tools and Algorithms for the Construction and Analysis of Systems. 1996

    1996

  205. [218]

    Meyer and Salomon Sickert and Michael Luttenberger , editor =

    Philipp J. Meyer and Salomon Sickert and Michael Luttenberger , editor =. Strix: Explicit Reactive Synthesis Strikes Back! , booktitle =. 2018 , url =. doi:10.1007/978-3-319-96145-3\_31 , timestamp =

    2018 doi

  206. [219]

    Solving parity games by a reduction to SAT , journal =

    Keijo Heljanko and Misa Keinänen and Martin Lange and Ilkka Niemelä , keywords =. Solving parity games by a reduction to SAT , journal =. 2012 , note =. doi:https://doi.org/10.1016/j.jcss.2011.05.004 , url =

    2012 doi

  207. [220]

    2010 , url=

    Solving Parity Games on the Playstation 3 , author=. 2010 , url=

    2010

  208. [221]

    Solving Parity Games in Practice

    Friedmann, Oliver and Lange, Martin. Solving Parity Games in Practice. Automated Technology for Verification and Analysis. 2009

    2009

  209. [222]

    Swen Jacobs and Guillermo A. Perez and Remco Abraham and Veronique Bruyere and Michael Cadilhac and Maximilien Colange and Charly Delfosse and Tom van Dijk and Alexandre Duret-Lutz and Peter Faymonville and Bernd Finkbeiner and Ayrat Khalimov and Felix Klein and Michael Lutten...

    arXiv

  210. [223]

    Parameterized Algorithms for Parity Games , booktitle =

    Jakub Gajarsk. Parameterized Algorithms for Parity Games , booktitle =. 2015 , url =. doi:10.1007/978-3-662-48054-0\_28 , timestamp =

    2015 doi

  211. [224]

    Burch and Edmund M

    Jerry R. Burch and Edmund M. Clarke and Kenneth L. McMillan and David L. Dill and L. J. Hwang , title =. Inf. Comput. , volume =. 1992 , url =. doi:10.1016/0890-5401(92)90017-A , timestamp =

    1992 doi

  212. [225]

    Meyer and Salomon Sickert , title =

    Michael Luttenberger and Philipp J. Meyer and Salomon Sickert , title =. Acta Informatica , volume =. 2020 , url =. doi:10.1007/s00236-019-00349-3 , timestamp =

    2020 doi

  213. [226]

    A Subexponential Lower Bound for

    Oliver Friedmann , editor =. A Subexponential Lower Bound for. IPCO , series =. 2011 , url =. doi:10.1007/978-3-642-20807-2\_16 , timestamp =

    2011 doi

  214. [227]

    CAV 2000 , year =

    V\"oge, Jens and Jurdzi\'nski, Marcin , title =. CAV 2000 , year =

    2000

  215. [228]

    Synthesis of Reactive(1) Designs

    Piterman, Nir and Pnueli, Amir and Sa'ar, Yaniv. Synthesis of Reactive(1) Designs. Verification, Model Checking, and Abstract Interpretation. 2006

    2006

  216. [229]

    A Discrete Subexponential Algorithm for Parity Games

    Bj \"o rklund, Henrik and Sandberg, Sven and Vorobyov, Sergei. A Discrete Subexponential Algorithm for Parity Games. STACS 2003. 2003

    2003

  217. [230]

    2024 , issn =

    Entropic risk for turn-based stochastic games , journal =. 2024 , issn =. doi:https://doi.org/10.1016/j.ic.2024.105214 , author =

    2024

  218. [231]

    Computer Science Logic, 18th International Workshop,

    Krishnendu Chatterjee and Rupak Majumdar and Marcin Jurdzinski , title =. Computer Science Logic, 18th International Workshop,. 2004 , doi =

    2004

  219. [232]

    Alexander Yakhnis and Vladimir Yakhnis , title =. Ann. Pure Appl. Log. , volume =. 1990 , url =. doi:10.1016/0168-0072(90)90024-V , timestamp =

    1990 doi

  220. [233]

    Information Processing Letters , volume=

    Fast and simple nested fixpoints , author=. Information Processing Letters , volume=. 1996 , publisher=

    1996

  221. [234]

    2011 , MONTH = Sep, KEYWORDS =

    Michael Ummels and Dominik Wojtczak , URL =. 2011 , MONTH = Sep, KEYWORDS =. doi:10.2168/LMCS-7(3:20)2011 , JOURNAL =

    2011 doi

  222. [235]

    Automated Verification Techniques for Probabilistic Systems

    Forejt, Vojt e ch and Kwiatkowska, Marta and Norman, Gethin and Parker, David. Automated Verification Techniques for Probabilistic Systems. Formal Methods for Eternal Networked Software Systems: 11th International School on Formal Methods for the Design of Computer, Communicat...

    2011 doi

  223. [236]

    Incremental plan aggregation for generating policies in

    Teichteil-K\". Incremental plan aggregation for generating policies in. Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1 - Volume 1 , pages =. 2010 , isbn =

    2010

  224. [237]

    and Jhala, Ranjit

    de Alfaro, Luca and Henzinger, Thomas A. and Jhala, Ranjit. Compositional Methods for Probabilistic Systems. CONCUR 2001 --- Concurrency Theory. 2001

    2001

  225. [238]

    From Variance to Value at Risk: A Unified Perspective on Standardized Risk Measures

    Brachinger, Hans Wolfgang. From Variance to Value at Risk: A Unified Perspective on Standardized Risk Measures. Classification in the Information Age. 1999

    1999

  226. [239]

    IEEE Transactions on Automatic Control , volume=

    On finite-state stochastic modeling and secure estimation of cyber-physical systems , author=. IEEE Transactions on Automatic Control , volume=. 2016 , publisher=

    2016

  227. [240]

    and Sun Wen

    Agarwal Alekh and Jiang, Nan and Kakade, Sham M. and Sun Wen. Reinforcement Learning: Theory and Algorithms. 2021

    2021

  228. [241]

    Convex measures of risk and trading constraints , journal=

    F. Convex measures of risk and trading constraints , journal=. 2002 , month=

    2002

  229. [242]

    2018 , publisher=

    Hands-On Value-at-Risk and Expected Shortfall: A Practical Primer , author=. 2018 , publisher=

    2018

  230. [243]

    Coherent Measures of Risk , volume =

    Artzner, Philippe and Delbaen, Freddy and Jean-Marc, Eber and Heath, David , year =. Coherent Measures of Risk , volume =. Mathematical Finance , doi =

  231. [244]

    49th International Colloquium on Automata, Languages, and Programming,

    Jakob Piribauer and Ocan Sankur and Christel Baier , title =. 49th International Colloquium on Automata, Languages, and Programming,. 2022 , doi =

    2022

  232. [245]

    Variance-Penalized Markov Decision Process , volume =

    Filar, Jerzy and Kallenberg, Lodewijk , year =. Variance-Penalized Markov Decision Process , volume =. Mathematics of Operations Research , doi =

  233. [246]

    Tsitsiklis , title =

    Shie Mannor and John N. Tsitsiklis , title =. Proceedings of the 28th International Conference on Machine Learning,. 2011 , url =

    2011

  234. [247]

    Variations on the Stochastic Shortest Path Problem

    Randour, Mickael and Raskin, Jean-Fran c ois and Sankur, Ocan. Variations on the Stochastic Shortest Path Problem. Verification, Model Checking, and Abstract Interpretation. 2015

    2015

  235. [248]

    Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes , year =

    K. Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes , year =. doi:10.1145/3209108.3209176 , booktitle =

  236. [249]

    Howard and James E

    Ronald A. Howard and James E. Matheson , journal =. Risk-Sensitive Markov Decision Processes , volume =

  237. [250]

    More Risk-Sensitive Markov Decision Processes , urldate =

    Nicole Bäuerle and Ulrich Rieder , journal =. More Risk-Sensitive Markov Decision Processes , urldate =

  238. [251]

    Nash , title =

    John F. Nash , title =. Proceedings of the National Academy of Sciences , volume =. 1950 , doi =

    1950

  239. [252]

    Repeated Games

    Aumann, Robert J. Repeated Games. Issues in Contemporary Microeconomics and Welfare. 1985. doi:10.1007/978-1-349-06876-0_5

    1985 doi

  240. [253]

    and Kjeldgaard-Pedersen, J

    Allender, E. and Kjeldgaard-Pedersen, J. and Burgisser, P. and Miltersen, P. , booktitle=. On the complexity of numerical analysis , year=

  241. [254]

    The Odds of Staying on Budget

    Haase, Christoph and Kiefer, Stefan. The Odds of Staying on Budget. Automata, Languages, and Programming. 2015

    2015

  242. [255]

    Proceedings of the AAAI Conference on Artificial Intelligence , pages =

    Tobias Meggendorfer , title =. Proceedings of the AAAI Conference on Artificial Intelligence , pages =. 2022 , doi =

    2022

  243. [256]

    Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy , booktitle =

    S. Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy , booktitle =

  244. [257]

    Continuity of the value of competitive

    Solan, Eilon , journal=. Continuity of the value of competitive. 2003 , publisher=

    2003

  245. [258]

    50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) , pages =

    Brice, L\'. 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) , pages =. 2025 , volume =

    2025

  246. [259]

    Winning Concurrent Reachability Games Requires Doubly-Exponential Patience , booktitle =

    Kristoffer Arnsfelt Hansen and Michal Kouck. Winning Concurrent Reachability Games Requires Doubly-Exponential Patience , booktitle =

  247. [260]

    Ali Asadi and Léonard Brice and Krishnendu Chatterjee and K. S. Thejaswini , year=. 2508.15356 , archivePrefix=

  248. [261]

    Optimal Control of a Birth and Death Epidemic Process , urldate =

    Claude Lefèvre , journal =. Optimal Control of a Birth and Death Epidemic Process , urldate =

  249. [262]

    2007 , note =

    Concurrent reachability games , journal =. 2007 , note =. doi:https://doi.org/10.1016/j.tcs.2007.07.008 , author =

    2007 doi

  250. [263]

    , journal=

    Belta, Calin and Bicchi, Antonio and Egerstedt, Magnus and Frazzoli, Emilio and Klavins, Eric and Pappas, George J. , journal=. Symbolic planning and control of robot motion [Grand Challenges of Robotics] , year=

  251. [264]

    Wooldridge , title =

    Julian Gutierrez and Muhammad Najib and Giuseppe Perelli and Michael J. Wooldridge , title =. Artif. Intell. , volume =. 2020 , url =. doi:10.1016/J.ARTINT.2020.103353 , timestamp =

    2020

  252. [265]

    2008 , url =

    Marius Kloetzer and Calin Belta , title =. 2008 , url =. doi:10.1109/TAC.2007.914952 , timestamp =

    2008

  253. [266]

    The Complexity of Nash Equilibria in Limit-Average Games , booktitle =

    Michael Ummels and Dominik Wojtczak , editor =. The Complexity of Nash Equilibria in Limit-Average Games , booktitle =. 2011 , url =. doi:10.1007/978-3-642-23217-6\_32 , timestamp =

    2011 doi

  254. [267]

    Patricia Bouyer and Romain Brenguier and Nicolas Markey and Michael Ummels , title =. Log. Methods Comput. Sci. , volume =. 2015 , url =. doi:10.2168/LMCS-11(2:9)2015 , timestamp =

    2015 doi

  255. [268]

    Canny , editor =

    John F. Canny , editor =. Some Algebraic and Geometric Computations in. Proceedings of the 20th Annual. 1988 , url =. doi:10.1145/62212.62257 , timestamp =

    1988

  256. [269]

    2006 , publisher=

    Algorithms in Real Algebraic Geometry , author=. 2006 , publisher=. doi:10.1007/978-3-540-30140-0 , edition=

    2006 doi

  257. [270]

    Puterman , title =

    Martin L. Puterman , title =. 1994 , url =. doi:10.1002/9780470316887 , isbn =

    1994 doi

  258. [271]

    Multi-Objective Model Checking of Markov Decision Processes , volume =

    Etessami, Kousha and Kwiatkowska, Marta and Vardi, Moshe and Yannakakis, Mihalis , year =. Multi-Objective Model Checking of Markov Decision Processes , volume =. Logical Methods in Computer Science , doi =

  259. [272]

    Journal of the ACM (JACM) , volume=

    On the combinatorial and algebraic complexity of quantifier elimination , author=. Journal of the ACM (JACM) , volume=. 1996 , publisher=

    1996

  260. [273]

    CoRR , volume =

    Marcus Schaefer and Jean Cardinal and Tillmann Miltzow , title =. CoRR , volume =. 2024 , url =. doi:10.48550/ARXIV.2407.18006 , eprinttype =. 2407.18006 , timestamp =

    2024 doi arXiv

  261. [274]

    Competitive Markov Decision Processes

    Jerzy Filar and Koos Vrieze. Competitive Markov Decision Processes

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.