Pierre Ohlmann
YOU?
Author Swipe
View article: Infinite lexicographic products of positional objectives
Infinite lexicographic products of positional objectives Open
This paper contributes to the study of positional determinacy of infinite duration games played on potentially infinite graphs. Recently, [Ohlmann, TheoretiCS 2023] established that positionality of prefix-independent objectives is preserv…
View article: Characterising memory in infinite games
Characterising memory in infinite games Open
This paper is concerned with games of infinite duration played over potentially infinite graphs. Recently, Ohlmann (LICS 2022) presented a characterisation of objectives admitting optimal positional strategies, by means of universal graphs…
View article: The memory of $ω$-regular and BC($Σ_2^0$) objectives
The memory of $ω$-regular and BC($Σ_2^0$) objectives Open
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 by Eve, she has a strategy with <= k states of memory. For …
View article: Graphs of unbounded linear cliquewidth must transduce all trees
Graphs of unbounded linear cliquewidth must transduce all trees Open
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: if a class of graphs has unbounded linear cliquewidth, then it can prod…
View article: Fast Value Iteration: Solvers implemented in Oink
Fast Value Iteration: Solvers implemented in Oink Open
* Introduction To start, extract the artifact fvi-tacas25.tar.gz in the home directory: $ cd ~/ $ tar xvf fvi-tacas25.tar.bz2 This artifact contains a few scripts and archived versions of: - Oink, by Tom van Dijk, augmented with the algori…
View article: On the Monniaux Problem in Abstract Interpretation
On the Monniaux Problem in Abstract Interpretation Open
The Monniaux Problem in abstract interpretation asks, roughly speaking, whether the following question is decidable: Given a program P , a safety (e.g., non-reachability) specification \(\varphi\) , and an abstract domain of invariants \(\…
View article: A positional $\mathbfΠ^0_3$-complete objective
A positional $\mathbfΠ^0_3$-complete objective Open
We study zero-sum turn-based games on graphs. In this note, we show the existence of a game objective that is $\mathbfΠ^0_3$-complete for the Borel hierarchy and that is positional, i.e., for which positional strategies suffice for the fir…
View article: Rank-decreasing transductions
Rank-decreasing transductions Open
International audience
View article: Positional ω-regular languages
Positional ω-regular languages Open
International audience
View article: Positional $ω$-regular languages
Positional $ω$-regular languages Open
In the context of two-player games over graphs, a language $L$ is called positional if, in all games using $L$ as winning objective, the protagonist can play optimally using positional strategies, that is, strategies that do not depend on …
View article: Rank-decreasing transductions
Rank-decreasing transductions Open
We propose to study transformations on graphs, and more generally structures, by looking at how the cut-rank (as introduced by Oum) of subsets is affected when going from the input structure to the output structure. We consider transformat…
View article: Positionality in Σ⁰₂ and a Completeness Result
Positionality in Σ⁰₂ and a Completeness Result Open
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 Σ⁰₂ which are positional and admit a (strongly) neutral letter are ex…
View article: Positionality in Σ_0^2 and a completeness result
Positionality in Σ_0^2 and a completeness result Open
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 Σ_0^2 which are positional and admit a (strongly) neutral letter are …
View article: Positionality of mean-payoff games on infinite graphs
Positionality of mean-payoff games on infinite graphs Open
This short note establishes positionality of mean-payoff games over infinite game graphs by constructing a well-founded monotone universal graph.
View article: Hardness of monadic second-order formulae over succinct graphs
Hardness of monadic second-order formulae over succinct graphs Open
Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graphs given by succinct representations. Succint representation…
View article: Characterizing Positionality in Games of Infinite Duration over Infinite Graphs
Characterizing Positionality in Games of Infinite Duration over Infinite Graphs Open
We study turn-based quantitative games of infinite duration opposing two antagonistic players and played over graphs. This model is widely accepted as providing the adequate framework for formalizing the synthesis question for reactive sys…
View article: Flipper games for monadically stable graph classes
Flipper games for monadically stable graph classes Open
A class of graphs $\mathscr{C}$ is monadically stable if for any unary expansion $\widehat{\mathscr{C}}$ of $\mathscr{C}$, one cannot interpret, in first-order logic, arbitrarily long linear orders in graphs from $\widehat{\mathscr{C}}$. I…
View article: Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes
Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes Open
We use model-theoretic tools originating from stability theory to derive a result we call the Finitary Substitute Lemma, which intuitively says the following. Suppose we work in a stable graph class 𝒞, and using a first-order formula φ wit…
View article: Characterising memory in infinite games
Characterising memory in infinite games Open
This paper is concerned with games of infinite duration played over potentially infinite graphs. Recently, Ohlmann (LICS 2022) presented a characterisation of objectives admitting optimal positional strategies, by means of universal graphs…
View article: The Theory of Universal Graphs for Infinite Duration Games
The Theory of Universal Graphs for Infinite Duration Games Open
We introduce the notion of universal graphs as a tool for constructing algorithms solving games of infinite duration such as parity games and mean payoff games. In the first part we develop the theory of universal graphs, with two goals: s…
View article: Scaling Neural Program Synthesis with Distribution-Based Search
Scaling Neural Program Synthesis with Distribution-Based Search Open
We consider the problem of automatically constructing computer programs from input-output examples. We investigate how to augment probabilistic and neural program synthesis methods with new search algorithms, proposing a framework called d…
View article: A Technique to Speed up Symmetric Attractor-Based Algorithms for Parity Games
A Technique to Speed up Symmetric Attractor-Based Algorithms for Parity Games Open
The classic McNaughton-Zielonka algorithm for solving parity games has excellent performance in practice, but its worst-case asymptotic complexity is worse than that of the state-of-the-art algorithms. This work pinpoints the mechanism tha…
View article: Monotonic graphs for parity and mean-payoff games
Monotonic graphs for parity and mean-payoff games Open
In a parity game, Eve and Adam take turns in moving a token along the edges of a directed graph, which are labelled by integers called priorities. This interaction results in an infinite path, and Eve wins the game if the maximal priority …
View article: Controlling a random population
Controlling a random population Open
Bertrand et al. introduced a model of parameterised systems, where each agent is represented by a finite state system, and studied the following control problem: for any number of agents, does there exist a controller able to bring all age…
View article: Scaling Neural Program Synthesis with Distribution-based Search
Scaling Neural Program Synthesis with Distribution-based Search Open
We consider the problem of automatically constructing computer programs from input-output examples. We investigate how to augment probabilistic and neural program synthesis methods with new search algorithms, proposing a framework called d…
View article: On the ESL algorithm for solving energy games.
On the ESL algorithm for solving energy games. Open
We propose a variant of an algorithm introduced by Schewe and also studied by Luttenberger for solving parity or mean-payoff games. We present it over energy games and call our variant the ESL algorithm (for Energy-Schewe-Luttenberger). We…
View article: The GKK Algorithm is the Fastest over Simple Mean-Payoff Games
The GKK Algorithm is the Fastest over Simple Mean-Payoff Games Open
We study the algorithm of Gurvich, Khachyian and Karzanov (GKK algorithm) when it is ran over mean-payoff games with no simple cycle of weight zero. We propose a new symmetric analysis, lowering the $O(n^2 N)$ upper-bound of Pisaruk on the…
View article: New Algorithms for Combinations of Objectives using Separating Automata
New Algorithms for Combinations of Objectives using Separating Automata Open
The notion of separating automata was introduced by Bojanczyk and Czerwinski for understanding the first quasipolynomial time algorithm for parity games. In this paper we show that separating automata is a powerful tool for constructing al…