Search

• < Previous
• 1
• Next >

---

Timed Parity Games: Complexity and Robustness

Krishnendu Chatterjee ; Thomas A. Henzinger ; Vinayak S. Prabhu.

We consider two-player games played in real time on game structures with clocks where the objectives of players are described using parity conditions. The games are \emph{concurrent} in that at each turn, both players independently propose a time delay and an action, and the action with the shorter&nbsp;[&hellip;]

---

Aspect-oriented linearizability proofs

Soham Chakraborty ; Thomas A. Henzinger ; Ali Sezgin ; Viktor Vafeiadis.

Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on the identification of the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency&nbsp;[&hellip;]

---

Expressiveness and Closure Properties for Quantitative Languages

Krishnendu Chatterjee ; Laurent Doyen ; Thomas A Henzinger.

Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages~$L$ that assign to each word~$w$ a real number~$L(w)$. In the case of infinite words, the value of a run is naturally computed as the maximum, limsup, liminf, limit-average,&nbsp;[&hellip;]

---

Algorithms for Omega-Regular Games with Imperfect Information

Krishnendu Chatterjee ; Laurent Doyen ; Thomas A. Henzinger ; Jean-Francois Raskin.

We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller&nbsp;[&hellip;]

---

Determinacy in Discrete-Bidding Infinite-Duration Games

Milad Aghajohari ; Guy Avni ; Thomas A. Henzinger.

In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner of the game. Such games are central in formal methods since they model the interaction between a non-terminating system and its environment. In bidding games the players&nbsp;[&hellip;]

---