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
Thomas Colcombet ; Christof Löding.
We consider a new kind of interpretation over relational structures: finite sets interpretations. Those interpretations are defined by weak monadic second-order (WMSO) formulas with free set variables. They transform a given structure into a structure with a domain consisting of finite sets of […]
Published on May 4, 2007
Thomas Colcombet ; Daniela Petrişan.
In this paper we regard languages and their acceptors - such as deterministic or weighted automata, transducers, or monoids - as functors from input categories that specify the type of the languages and of the machines to categories that specify the type of outputs. Our results are as follows: A) […]
Published on March 23, 2020
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