Pith. sign in

REVIEW 5 cited by

Games on Graphs: From Logic and Automata to Algorithms

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2305.10546 v2 pith:3T3XASN2 submitted 2023-05-17 cs.GT cs.FLcs.LO

Nathanaël Fijalkow , C. Aiswarya , Guy Avni , Nathalie Bertrand , Patricia Bouyer , Romain Brenguier , Arnaud Carayol , Antonio Casares
show 17 more authors
John Fearnley Paul Gastin Hugo Gimbert Thomas A. Henzinger Florian Horn Rasmus Ibsen-Jensen Nicolas Markey Benjamin Monmege Petr Novotný Pierre Ohlmann Mickael Randour Ocan Sankur Sylvain Schmitz Olivier Serre Mateusz Skomra Nathalie Sznajder Pierre Vandenhove
This is my paper
classification cs.GTcs.FLcs.LO
keywords automatabookgamesgraphslogicmodelsresearchtheory
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

The objective of this book is to give a comprehensive presentation of the research field concerned with infinite duration games on graphs. Historically, these game models appeared in the study of automata and logic, and they later became important for program verification and synthesis. They have many more applications, in particular some of the models investigated in this book were introduced and studied in neighbouring research communities such as optimisation, reinforcement learning, model theory, and set theory.

Discussion (0). Sign in to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Multi-Player Discrete-Bidding Games; Determinacy, Equilibria, and Complexity

    cs.GT 2026-07 accept novelty 7.0 of 10

    Under linear tie-breaking, multi-player discrete-bidding games are determined, admit pure Nash equilibria and mean-payoff values, and deciding the winner is already PSPACE-hard for unary reachability.

  2. Ample sets in Cartesian products

    math.CO 2026-07 accept novelty 7.0 of 10

    Ample sets of Cartesian products are characterized by shattering-to-strong-shattering of minor-subproducts and inherit the main binary-case equivalences plus contractible prism complexes.

  3. Emerson-Lei and Manna-Pnueli Games for LTLf+ and PPLTL+ Synthesis

    cs.LO 2025-08 conditional novelty 7.0 of 10

    First implemented solvers for LTLf+ and PPLTL+ synthesis, with a new Manna-Pnueli game formalism solved by composing DAGs of Emerson-Lei games at a provably better worst-case bound.

  4. Simple Nash Equilibria for Qualitative Multiplayer Games

    cs.GT 2026-07 conditional novelty 6.0 of 10

    Memoryless randomised subgame-perfect equilibria always exist for turn-based deterministic games with reachability, safety, and 0-2 Muller objectives, and can be constructed in polynomial time.

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

    cs.LO 2025-09 accept novelty 3.0 of 10

    A survey of memory and randomness complexity for strategies in reactive synthesis, arguing that Mealy-machine-based measures of simplicity are representation-dependent.

Pith tools