Résumé : Les fonctions régulières de
coût ont été introduites comme
généralisation quantitative des langages réguliers,
dont elles conservent plusieurs caractérisations équivalentes
et propriétés de décidabilité. Par exemple, les
monoïdes de stabilisation jouent le même rôle pour les
fonctions de coûts que les monoïdes pour les langages
réguliers. Le but de cet article est d'étendre cette approche
algébrique en généralisant deux résultats sur
les langues réguliers aux fonctions de coût: le
théorème des variétés d'Eilenberg et les
caractérisations équationnelles profinies des treillis de
langages réguliers. Cela ouvre de nouvelles perspectives
intéressantes, mais les spécificités des fonctions de
coût introduisent des difficultés qui empêchent ces
généralisations d'être simples. En revanche, bien que
les algèbres syntaxiques puissent être définies pour
les séries formelles sur un anneau commutatif, une telle notion
semble manquer pour les séries sur un semi-anneau et en particulier
sur le semianneau tropical.
Abstract : Regular cost functions were introduced as a quantitative
generalisation of regular languages, retaining many of their equivalent
characterisations and decidability properties. For instance, stabilisation
monoids play the same role for cost functions as monoids do for regular
languages. The purpose of this article is to further extend this algebraic
approach by generalising two results on regular languages to cost
functions: Eilenberg's varieties theorem and profinite equational
characterisations of lattices of regular languages. This opens interesting
new perspectives, but the specificities of cost functions introduce
difficulties that prevent these generalisations to be straightforward. In
contrast, although syntactic algebras can be defined for formal power
series over a commutative ring, no such notion is known for series over
semirings and in particular over the tropical semiring.