An algorithm to rule them all: Fast value iteration for energy games

Speaker(s)

Antonio Casares

Affiliation

University of Warsaw

Language of the talk

English

Date

Oct. 16, 2024, 2:15 p.m.

Room

room 5440

Title in Polish

An algorithm to rule them all: Fast value iteration for energy games

Seminar

Seminar Automata Theory

---

We introduce a uniform framework for describing, comparing, 
and proving correctness of algorithms for energy games (which generalise 
the well known parity games). This framework allows us to provide simple 
presentations and correctness proofs of known algorithms including GKK 
(1988), Schewe (2008), BCDGR (2011) or BDM (2020). The new approach also 
leads to novel algorithms and plenty of exciting open questions and 
research directions! Based on joint work with Michaël Cadhilac and 
Pierre Ohlmann.

---