Quantitative Languages Defined by Functional Automata

Abstract : In this paper, we study several decision problems for functional weighted automata. To associate values with runs, we consider four different measure functions: the sum, the mean, the discounted sum of weights along edges and the ratio between rewards and costs. On the positive side, we show that the existential and universal threshold problems, the language inclusion problem and the equivalence problem are all decidable for the class of functional weighted automata and the four measure functions that we consider. On the negative side, we also study the quantitative extension of the realizability problem and show that it is undecidable for sum, mean and ratio. Finally, we show how to decide if the quantitative language defined by a functional weighted discounted sum automaton can be defined with a deterministic automata (it was already known for sum and mean).
Type de document :
[Technical Report] 2011, pp.27
Liste complète des métadonnées

Contributeur : Emmanuel Filiot <>
Soumis le : mardi 29 novembre 2011 - 19:45:56
Dernière modification le : vendredi 16 septembre 2016 - 15:17:05
Document(s) archivé(s) le : lundi 5 décembre 2016 - 05:44:20


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00626216, version 2
  • ARXIV : 1111.0862



Emmanuel Filiot, Raffaella Gentilini, Jean-François Raskin. Quantitative Languages Defined by Functional Automata. [Technical Report] 2011, pp.27. 〈inria-00626216v2〉



Consultations de la notice


Téléchargements de fichiers