Varieties of cost functions

Daviaud, Laure, Kuperberg, Denis and Pin, Jean Éric (2016) Varieties of cost functions. In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016. Leibniz International Proceedings in Informatics, LIPIcs . Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, FRA. ISBN 9783959770019

Full text not available from this repository.

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.

Item Type:	Book Section
Additional Information:	Publisher Copyright: © Laure Daviaud, Denis Kuperberg, and Jean-Éric Pin; licensed under Creative Commons License CC-BY.
Uncontrolled Keywords:	cost functions,regular language,syntactic algebra,varieties,software ,/dk/atira/pure/subjectarea/asjc/1700/1712
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	08 Jun 2023 13:30
Last Modified:	08 Jun 2023 13:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/92327
DOI:	10.4230/LIPIcs.STACS.2016.30

Actions (login required)

View Item