5 citations · 11 across the 10 of their papers we have counts for
5 papers · 1 filter
The Complexity of Infinitely Repeated Alternating Move Games
Yaron Velner
We consider infinite duration alternating move games. These games were previously studied by Roth, Balcan, Kalai and Mansour. They presented an FPTAS for computing an approximated…
Hyperplane Separation Technique for Multidimensional Mean-Payoff Games
Krishnendu Chatterjee, Yaron Velner
We consider both finite-state game graphs and recursive game graphs (or pushdown game graphs), that can model the control flow of sequential programs with recursion, with multi-dim…
The Complexity of Multi-Mean-Payoff and Multi-Energy Games
Yaron Velner, Krishnendu Chatterjee, Laurent Doyen +3
In mean-payoff games, the objective of the protagonist is to ensure that the limit average of an infinite sequence of numeric weights is nonnegative. In energy games, the objective…
Finite-Memory Strategy Synthesis for Robust Multidimensional Mean-Payoff Objectives
Yaron Velner
Two-player games on graphs provide the mathematical foundation for the study of reactive systems. In the quantitative framework, an objective assigns a value to every play, and the…
Mean-Payoff Pushdown Games
Krishnendu Chatterjee, Yaron Velner
Two-player games on graphs is central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solv…