Skip to Main content Skip to Navigation
Reports

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).
Complete list of metadata

https://hal.inria.fr/inria-00626216
Contributor : Emmanuel Filiot Connect in order to contact the contributor
Submitted on : Tuesday, November 29, 2011 - 7:45:56 PM
Last modification on : Tuesday, October 19, 2021 - 12:55:33 PM
Long-term archiving on: : Monday, December 5, 2016 - 5:44:20 AM

Files

main.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

47

Files downloads

317