3 citations · 4 across the 5 of their papers we have counts for
8 papers
Reachability Poorman Discrete-Bidding Games
Guy Avni, Tobias Meggendorfer, Suman Sadhukhan +2
We consider {\em bidding games}, a class of two-player zero-sum {\em graph games}. The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of…
Social Balance on Networks: Local Minima and Best Edge Dynamics
Krishnendu Chatterjee, Jakub Svoboda, Ðorđe Žikelić +2
Structural balance theory is an established framework for studying social relationships of friendship and enmity. These relationships are modeled by a signed network whose energy p…
Proving Non-termination by Program Reversal
Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný +1
We present a new approach to proving non-termination of non-deterministic integer programs. Our technique is rather simple but efficient. It relies on a purely syntactic reversal o…
Proving Almost-Sure Termination of Probabilistic Programs via Incremental Pruning
Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný +2
The extension of classical imperative programs with real-valued random variables and random branching gives rise to probabilistic programs. The termination problem is one of the mo…
Infinite-Duration All-Pay Bidding Games
Guy Avni, Ismaël Jecker, Đorđe Žikelić
In a two-player zero-sum graph game the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. Traditionally, the p…
Bidding Mechanisms in Graph Games
Guy Avni, Thomas A. Henzinger, Đorđe Žikelić
In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner or payoff of the game. We study {\em bidding games}…
Stochastic Invariants for Probabilistic Termination
Krishnendu Chatterjee, Petr Novotný, Đorđe Žikelić
Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the quali…
Optimizing Expectation with Guarantees in POMDPs (Technical Report)
Krishnendu Chatterjee, Petr Novotný, Guillermo A. Pérez +2
A standard objective in partially-observable Markov decision processes (POMDPs) is to find a policy that maximizes the expected discounted-sum payoff. However, such policies may st…