Quantitative Languages Defined by Functional Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport Technique) Année : 2011

Quantitative Languages Defined by Functional Automata

Résumé

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).
Fichier principal
Vignette du fichier
main.pdf (314.85 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00626216 , version 1 (23-09-2011)
inria-00626216 , version 2 (29-11-2011)

Identifiants

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

Citer

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

Collections

LARA
50 Consultations
341 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More