Search

• < Previous
• 1
• Next >

---

Regular Cost Functions, Part I: Logic and Algebra over Words

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

---

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

---

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

---