The Bridge Between Regular Cost Functions and Omega-Regular Languages
Thomas Colcombet, Nathanaël Fijalkow · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
In this paper, we exhibit a one-to-one correspondence between omega-regular languages and a subclass of regular cost functions over finite words, called omega-regular like cost functions. This bridge between the two models allows one to readily import classical results such as the last appearance record or the McNaughton-Safra constructions to the realm of regular cost functions. In combination with game theoretic techniques, this also yields a simple description of an optimal procedure of history-determinisation for cost automata, a central result in the theory of regular cost functions.