Search

• < Previous
• 1
• Next >

---

Transforming structures by set interpretations

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&nbsp;[&hellip;]

---

Automata Minimization: a Functorial Approach

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)&nbsp;[&hellip;]

---

The Theory of Universal Graphs for Infinite Duration Games

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&nbsp;[&hellip;]

---