Search

• < Previous
• 1
• Next >

---

Boundedness in languages of infinite words

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&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;]

---

Controlling a random population

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&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;]

---