7 papers
The complexity of downward closures of indexed languages
Richard Mandel, Corto Mascle, Georg Zetzsche
Indexed languages are a classical notion in formal language theory, which has attracted attention in recent decades due to its role in higher-order model checking: They are precise…
Population Protocols over Ordered Agents
Michael Blondin, Michaël Cadilhac, Benjamin Courchesne +3
Population protocols are a distributed computation model in which a collection of anonymous, finite-state agents interact in randomly chosen pairs and update their states according…
Optimally Controlling a Random Population
Hugo Gimbert, Corto Mascle, Patrick Totzke
The population control problem is a parameterised problem where a controller sends messages to a whole population of identical finite-state agents, aiming to eventually move them a…
Optimal Sequential Flows
Hugo Gimbert, Corto Mascle, Patrick Totzke
We provide a new algebraic technique to solve the sequential flow problem in polynomial space. The task is to maximise the flow through a graph where edge capacities can be changed…
Reach together: How populations win repeated games
Nathalie Bertrand, Patricia Bouyer, Luc Lapointe +1
In repeated games, players choose actions concurrently at each step. We consider a parameterized setting of repeated games in which the players form a population of an arbitrary si…
Distributed controller synthesis for deadlock avoidance
Hugo Gimbert, Corto Mascle, Anca Muscholl +1
We consider the distributed control synthesis problem for systems with locks. The goal is to find local controllers so that the global system does not deadlock. With no restriction…