Quantitative Languages Defined by Functional Automata - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Technical Report) Year : 2011

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).
Fichier principal
Vignette du fichier
main.pdf (314.85 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

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

Cite

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

Collections

LARA
52 View
342 Download

Altmetric

Share

Gmail Facebook X LinkedIn More