Constructions à la Safra pour les fonctions régulières de coût sur les mots finis
Thomas Colcombet · HAL (Le Centre pour la Communication Scientifique Directe) · 2011
Regular cost functions have been introduced recently as an extension of the notion of regular languages with counting capabilities, which retains strong closure, equivalence, and decidability properties. Cost functions are functions ranging over N ∪ {∞}, and considered mod-ulo an equivalence which preserves the existence of bounds over each subset of the domain. A central result in the theory of regular cost functions over words is the duality theorem stating that the two dual forms of automata, namely Band S-automata, are equivalent. The only known proof of this result relies on the translation into an equivalent algebraic formalism.In this paper, we describe direct translations from hierarchical B-automata to history-deterministic S-automata and from hierarchical S-automata to history deterministic B-automata. We furthermore describe how to optimize the number of counters of the output automaton, and how to make them hierarchical. This construction is reminiscent of the famous construction of Safra for the determinization of automata over infinite words.