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

---

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

---

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

---

Playing Safe, Ten Years Later

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

---