Varieties of cost functions

L. Daviaud, D. Kuperberg, J.-É. Pin



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.

PDF file

Valid HTML 4.01!