4 results
Nathanaël Fijalkow ; Stefan Kiefer ; Mahsa Shirmohammadi.
Given two labelled Markov decision processes (MDPs), the trace-refinement problem asks whether for all strategies of the first MDP there exists a strategy of the second MDP such that the induced labelled Markov chains are trace-equivalent. We show that this problem is decidable in polynomial time if […]
Published on June 3, 2020
Nathanaël Fijalkow ; Hugo Gimbert ; Edon Kelmendi ; Youssouf Oualhadj.
The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton, are there words accepted with probability arbitrarily close to 1? This problem was proved undecidable recently; to overcome this, several classes of probabilistic automata of […]
Published on June 23, 2015
Thomas Colcombet ; Nathanaël Fijalkow ; Pierre Ohlmann.
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 agents to a target state? They showed that the problem is […]
Published on November 24, 2021
Thomas Colcombet ; Nathanaël Fijalkow ; Paweł Gawrychowski ; Pierre Ohlmann.
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: showing an equivalence and normalisation result between […]
Published on September 7, 2022