11 papers
Trees in graphs of large linear cliquewidth
MikoÅaj BojaÅczyk, Pierre Ohlmann
The Pathwidth Theorem states that if a class of graphs has unbounded pathwidth, then it contains all trees as graph minors. We prove a similar result for dense graphs. More precise…
The memory of -regular and BC() objectives
Antonio Casares, Pierre Ohlmann
In the context of 2-player zero-sum infinite-duration games played on (potentially infinite) graphs, the memory of an objective is the smallest integer k such that in any game won…
Infinite lexicographic products of positional objectives
Antonio Casares, Pierre Ohlmann, MichaÅ Skrzypczak +1
This paper contributes to the study of positional determinacy of infinite duration games played on potentially infinite graphs with neutral transitions. Recently, [Ohlmann, Theoret…
Expregular functions
Thomas Colcombet, Nathan Lhote, Pierre Ohlmann
Polyregular functions form a robust class of string-to-string functions with polynomial growth, as evidenced by Bojanczyk (2018). This class admits numerous descriptions and enjoys…
Positionality in and a completeness result
Pierre Ohlmann, MichaÅ Skrzypczak
We study the existence of positional strategies for the protagonist in infinite duration games over arbitrary game graphs. We prove that prefix-independent objectives in w…
A symmetric recursive algorithm for mean-payoff games
Pierre Ohlmann
We propose a new deterministic symmetric recursive algorithm for solving mean-payoff games.