4 results
Thomas Colcombet.
The theory of regular cost functions is a quantitative extension to the classical notion of regularity. A cost function associates to each input a non-negative integer value (or infinity), as opposed to languages which only associate to each input the two values "inside" and "outside". This theory […]
Published on August 13, 2013
Mikołaj Bojańczyk ; Thomas Colcombet.
We define a new class of languages of $\omega$-words, strictly extending $\omega$-regular languages. One way to present this new class is by a type of regular expressions. The new expressions are an extension of $\omega$-regular expressions where two new variants of the Kleene star $L^*$ are […]
Published on October 26, 2017
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 ; Florian Horn.
We consider two-player games over graphs and give tight bounds on the memory size of strategies ensuring safety objectives. More specifically, we show that the minimal number of memory states of a strategy ensuring a safety objective is given by the size of the maximal antichain of left quotients […]
Published on January 29, 2024