Varieties of cost functions

Laure Daviaud, Denis Kuperberg, Jean Éric Pin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)


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.

Original languageEnglish
Title of host publication33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016
EditorsHeribert Vollmer, Nicolas Ollinger
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770019
Publication statusPublished - 1 Feb 2016
Externally publishedYes
Event33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 - Orleans, France
Duration: 17 Feb 201620 Feb 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016


  • Cost functions
  • Regular language
  • Syntactic algebra
  • Varieties

Cite this