Graph-based games are an important tool in computer science. They have applications in
synthesis, verification, refinement, and far beyond. We review graph-based games with …

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 is to …

We generalise the hyperplane separation technique (Chatterjee and Velner, 2013) from
multi-dimensional mean-payoff to energy games, and achieve an algorithm for solving the …

We consider partially observable Markov decision processes (POMDPs) modeling an agent
that needs a supply of a certain resource (eg, electricity stored in batteries) to operate …

Abstract Consumption Markov Decision Processes (CMDPs) are probabilistic decision-
making models of resource-constrained systems. In a CMDP, the controller possesses a …

This book constitutes the proceedings of the 26th International Conference on Computer
Aided Verification, CAV 2014, held as part of the Vienna Summer of Logic, VSL 2014, in …

We consider the logic MSO+ U, which is monadic second-order logic extended with the
unbounding quantifier. The unbounding quantifier is used to say that a property of finite sets …

We consider finite-state and recursive game graphs with multidimensional mean-payoff
objectives. In recursive games two types of strategies are relevant: global strategies and …

We consider two-player games played on finite graphs equipped with costs on edges and
introduce two winning conditions, cost-parity and cost-Streett, which require bounds on the …

This paper shows that over infinite trees, satisfiability is decidable for weak monadic second-
order logic extended by the unbounding quantifier \mathsfU and quantification over infinite …